Leetcode：三数之和 Java 实现 讲解非常详细

1. 题目：

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

注意：答案中不可以包含重复的三元组。

例如， 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

2. 解题思路

（1）先考虑将 nums 进行排序；
（2）将 nums[i] 作为第一个加数，从 i+1 到 nums.length – 1 之间初始化两个指针 j、k ，为了避免有重复的情况，当 nums[i] == nums[i-1] ，说明有重复的情况，开始下一个循环；
（3）如果 num[i] + num[j] + num[k] > target，说明加多了，让 k-–；
（4）如果 num[i] + num[j] + num[k] < target，说明加少了，让 j++；
（5）如果等于 target ，说明符合条件，将这一组解加到集合中，这时也应该避免第二个加数和第三个加数重复的情况。

3. Java 实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class threeSum {
    public List<List<Integer>> threeSum_fuction(int[] nums,int target){
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(int i = 0;i < nums.length-2;i++)
        {
            if(i>0&&nums[i] == nums[i-1])
                continue;
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                if(nums[i] + nums[j] + nums[k] == target)
                {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(nums[k]);
                    result.add(list);
                    while(j<k&&nums[j]==nums[j+1])
                        j++;
                    while(j<k&&nums[k]==nums[k-1])
                        k--;
                    j++;
                    k--;
                }
                else if(nums[i] + nums[j] + nums[k] < target)
                {
                    j++;
                }
                else if(nums[i] + nums[j] + nums[k] > target)
                {
                    k--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args)
    {
        int[] nums = new int[]{-1, 0, 1, 0, 1, 1};
        int target = 3;
        threeSum S = new threeSum();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        result = S.threeSum_fuction(nums,target);
        System.out.println(result);
    }
}