# 13. 三数之和

java

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

/**
 * 15. 三数之和
 *
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 *
 * 满足要求的三元组集合为：
 * [
 *   [-1, 0, 1],
 *   [-1, -1, 2]
 * ]
 */
public class Solution15 {

    /**
     * 双指针：先排序，然后指定第一个数，求解后面两数之和等于该数的相反数
     * i指向第一个数之后的一个数，j指向末尾
     * 如果此时三数之和等于0，那么将三个数记录
     * 如果三数之和>0，j向前移动
     * 如果三数之和<0，i向后移动
     *
     * 注意去重
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> r=new ArrayList<>();
        Arrays.sort(nums);
        for(int i=0;i<nums.length-2;i++){
            int k=i+1;//前指针：指向第2个数
            int v=nums.length-1;//后指针：指向第3个数
            if(nums[i]>0) continue;
            //以下一行用来去重
            if(i>0&&nums[i]==nums[i-1]) continue;

            while(k<v){
                int sum=nums[i]+nums[k]+nums[v];
                if(sum==0){
                    r.add(Arrays.asList(nums[i],nums[k],nums[v]));
                    //以下两行用来去重
                    while(k<v&&nums[k]==nums[k+1]) k++;
                    while(k<v&&nums[v]==nums[v-1]) v--;
                    v--;
                    k++;
                }else if(sum>0){
                    v--;
                }else{
                    k++;
                }
            }
        }
        return r;
    }

    public static void main(String[] args){
        int[] nums={
                -4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0
        };
        List<List<Integer>> r=new Solution15().threeSum(nums);
        for(List<Integer> l:r){
            for(Integer i:l){
                System.out.print(i+" ");
            }
            System.out.println();
        }
    }
}
```

python

```python
'''
在数组中找到3个元素的索引，满足和为k,且找到多个解
'''


class Solution:
    def call(self, nums, target):
        '''
        在nums中找到两个数，满足和为target
        :param nums:
        :param target:
        :return:
        '''
        hashset = {}
        res = []
        for i, m in enumerate(nums):
            if target - m not in hashset:
                hashset[m] = i
            else:
                res.append([hashset[target - m], i])
        return res

    def call2(self, nums, k):
        '''
        在nums中找到3个数，满足和为k
        :param nums:
        :param k:
        :return:
        '''
        if len(nums) < 3:
            return nums
        result = []
        for i in range(len(nums) - 1):
            target = k - nums[i]
            # 避免重复，从后面的数组开始寻找
            s = self.call(nums[i + 1:], target)
            if len(s) != 0:
                for p in s:
                    # ss = [nums[i], nums[i + p[0] + 1], nums[i + p[1] + 1]]
                    ss = [i, i + p[0] + 1, i + p[1] + 1]
                    if ss not in result:
                        result.append(ss)
        return result


s = Solution()
print(s.call2([-1, 0, 1, 2, -1, -4], -1))

#[[0, 2, 4], [2, 3, 5]]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/shua-ti/zhi-shang-lei/13-san-shu-zhi-he.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.