15.三数之和.md

15. 三数之和

url

题目

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

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

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
输入：nums = []
输出：[]
输入：nums = [0]
输出：[]

方法

code

js

let treeSum = nums => {
    let ret = [];
    if (nums === null || nums.length === 0)
        return ret;
    nums.sort();
    for (let i = 0; i < nums.length - 2; i++) {
        if (nums[i] > 0)
            break;
        if (i !== 0 && nums[i] === nums[i - 1])
            continue;
        let l = i + 1, r = nums.length - 1;
        while (l < r) {
            let sum = nums[l] + nums[r];
            if (sum < -nums[i])
                l++;
            else if (sum > -nums[i])
                r--;
            else {
                ret.push([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--;
            }
        }
    }
    return ret;
};

go

func threeSum(nums []int) [][]int {
	res := make([][]int, 0)
	if nums == nil || len(nums) == 0 {
		 return res
	}
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		if nums[i] > 0 {
			break
		}
		if i != 0 && nums[i] == nums[i-1] {
			continue
		}
		l, r := i + 1, len(nums) - 1
		for l < r {
			sum := nums[l] + nums[r]
			if sum < -nums[i] {
				l++
			} else if sum > -nums[i] {
				r--
			} else {
				res = append(res, []int{nums[i], nums[l], nums[r]})
				for l < r && nums[l] == nums[l+1] {
					l++
				}
				for l < r && nums[r] == nums[r-1] {
					r--
				}
				l++
				r--
			}
		}
	}
	return res
}

java

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if (nums == null || nums.length == 0)
            return ret;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++){
            if (nums[i] > 0)
                break;
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int l = i + 1, r = nums.length - 1;
            while (l < r){
                int sum = nums[l] + nums[r];
                if (sum < -nums[i])
                    l++;
                else if (sum > -nums[i])
                    r--;
                else {
                    ret.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--;
                }
            }
        }
        return ret;
    }   
}