刷算法(7)-三数之和

15. 三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。

解法

public List<List<Integer>> threeSum(int[] nums) {

    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++){
        if (nums[i] > 0) break;
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int left = i+1, right = nums.length - 1;
        while (left < right){
            int sum = nums[i] + nums[left] + nums[right];
            if ( sum == 0){
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[right] == nums[right-1]) right--;
                while (left < right && nums[left] == nums[left+1]) left++;
                left++;
                right--;
            }else if (sum > 0){
                right--;
            }else{
                left++;
            }
        }
    }

    return result;
}

心得

1. 整体思路是先对数组进行排序，然后对有序数组依次查找，用最左、最右两个指针索引进行遍历;
2. 因为数组是递增的，一旦num[i] > 0则对索引i就不需要再找了需要结束整个流程(因为i右边的数都比它大)；
3. 如果遍历到i，但是num[i]等于num[i-1]，则忽略这个i，从i的下一个开始找，通过for循环控制；
4. 针对i，定义left和right，在left和right区间去找，计算三者sum；
5. 如果sum = 0，则放到结果里，同时对left和right，判断是否有重复的，如果有重复的就往前/往后移位。这里有两个注意事项：

• 1)注意是通过left和left+1比的，意味着出while后，left指的位置仍然是当下参与计算sum的那个索引，出循环后left和right要进行递增、递减操作，这一切都归功于数组是递增有序的；
• 2)注意while循环的条件一定有left < right，这一点非常关键；

6. 如果sum > 0意味着值太大了，需要小点，那就把right递减下；
7. 如果sum < 0意味着太小了，需要更大，那就把left递增加大下这个值，因为right是从最右边来的，已经是最大的了；

参考

• 画解算法：15. 三数之和