三数之和

原题链接

使用到的方法

• Arrays.sort(): 对数组进行排序。
• Arrays.asList(): 将数组转换为列表。

解题思路

• 首先对数组进行排序，以便后续使用双指针法。(这里可以对边界条件进行优化：如果给的数组长度小于3 或 数组为null，直接返回)
• 遍历排序后的数组
• 外层循环：固定一个元素，剪枝、去重
  • 如果当前元素大于0，由于数组是排序的，后续元素也会大于0，因此不可能找到三个数的和为0，直接结束循环。
  • 如果当前元素与前一个元素相同，为了避免重复结果，跳过当前元素。
• 内层循环：使用双指针法寻找剩余两个数，使得三数之和为0。
  • 初始化两个指针，l指向当前元素的下一个位置，r指向数组的末尾。
  • 计算当前三个数的和，如果和为0，则将这三个数添加到结果列表中，并跳过重复元素，移动两个指针。
  • 如果和小于0，说明需要更大的数，将左指针右移。
  • 如果和大于0，说明需要更小的数，将右指针左移。
• 重复上述步骤，直到所有元素都被处理完。

代码实现

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums);

        for(int i = 0;i < len;i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i-1]) continue;
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum  = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while(L<R && nums[L] == nums[L+1]) L++;
                    while(L<R && nums[R] == nums[R-1]) R--;
                    L++;
                    R--;
                }
                else if(sum < 0) L++;
                else if(sum > 0) R--;
            }
        }
        return ans;
    }
}