Day2

15.3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

实现思路

• 如何快速找出3个数的和为0
  先排序，从头开始遍历，选定一个元素，然后再后从首尾取数，最终选定剩余的两个元素
• 找出的结果要保证是不重复的
  查找过程中，对于相同的数进行排除

实现代码

public class Solution {
    /*要考虑的问题：
        如何快速找出3个数的和为0；先排序，从头开始遍历，选定一个元素，然后再后从首尾取数，最终选定剩余的两个元素
        找出的结果要保证是不重复的；查找过程中，对于相同的数进行排除
    */
    public List<List<Integer>> threeSum(int[] nums) {
        //将数组进行排序
        Arrays.sort(nums);
        
        List<List<Integer>> rs = new LinkedList<>();
        
        for(int i = 0; i < nums.length - 2; i ++){
            int sum = 0 - nums[i];
            //若前后的元素一致，那么可以跳过该操作
            if(i == 0 ||(i > 0 && nums[i] != nums[i-1])){
                int lo = i+1;
                int hi = nums.length-1;
                //首尾搜索
                while(lo < hi){
                    //获得结果，则添加
                    if(nums[lo]+nums[hi] == sum){
                        rs.add(Arrays.asList(nums[i],nums[lo],nums[hi]));
                        //将相同的元素忽略掉
                        while(lo<hi && nums[lo] == nums[lo+1]) lo ++;
                        while(lo<hi && nums[hi] == nums[hi-1]) hi --;
                        lo ++; hi --;
                    } else if (nums[lo]+nums[hi] < sum)
                        lo ++;
                    else 
                        hi --;
                }
            }
        }
        return rs;
    }
}