力扣-三数之和

文章目录

• • 题目
  • 题解

题目

原题链接：三数之和

题解

思路：一层枚举+双指针

public class Test {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3) return res;
        Arrays.sort(nums);
        int target = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            //因为数组排序了 如果num[i]大于0  则后面不可能选出三个数和为0
            if (nums[i] > 0) break;
            target = 0 - nums[i];
            int l = i + 1, h = nums.length - 1;
            while (l < h) {
                if (nums[l] + nums[h] > target) {
                    h--;
                } else if (nums[l] + nums[h] < target) {
                    l++;
                } else if (nums[l] + nums[h] == target) {
                     // 跳过重复元素
                    while (l < h && nums[l] == nums[l + 1]) l++;
                    while (l < h && nums[h] == nums[h - 1]) h--;
                    res.add(new ArrayList<>(Arrays.asList(nums[i], nums[l], nums[h])));
                    h--;
                    l++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(threeSum(nums));
    }
}

while里面的去重， 可以用下面两种方法。（为什么去重？看一个数组[-2, 0, 0, 2, 2]）

 // 跳过重复元素
 while (l < h && nums[l] == nums[l + 1]) l++;
 while (l < h && nums[h] == nums[h - 1]) h--;


if (nums[l] == nums[l - 1] && ((h + 1) < nums.length && nums[h] == nums[h + 1])) {
              l++;
              h--;
              continue;
}

❤觉得有用的可以留个关注~~❤