描述

分析

排序+双指针
直接看代码。

代码

public static List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for(int k = 0; k < nums.length - 2; k++){
        if(nums[k] > 0) break; // 此时只有k位置的元素都大于0了，不可能存在三数之和为0
        if(k > 0 && nums[k] == nums[k - 1]) continue; // 排除相等的元素，不重复计算
        int i = k + 1, j = nums.length - 1; // 初始化两个指针
        while(i < j){ // 指针变化
            int sum = nums[k] + nums[i] + nums[j]; // 计算和
            if(sum < 0){
                // 指针往右
                while(i < j && nums[i] == nums[++i]); // 同样排除相等的元素
            } else if (sum > 0) {
                // 指针往左
                while(i < j && nums[j] == nums[--j]); // 同样排除相等的元素
            } else {
                // 找到和为0 的，下一轮
                res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                while(i < j && nums[i] == nums[++i]); // 同样排除相等的元素
                while(i < j && nums[j] == nums[--j]);
            }
        }
    }
    return res;
}

面试公司