数据结构与算法之LeetCode-15-三数之和

数据结构与算法之二叉树遍历(Javascript递归实现)
数据结构与算法之深度遍历与广度遍历（DFS&BFS）
数据结构与算法之LeetCode 844. 比较含退格的字符串
LeetCode-1404 将二进制表示减到1的步骤数
LeetCode-653-两数之和IV（利用中序遍历递归求解）

二分法 先确定一个初始位置
再用下一个位置，与最后的位置开始二分搜索
不断向中间搜索确定一个终止位置

var threeSum = function(nums) {
    let ans = [];
    const len = nums.length;
    if(nums == null || len < 3) return ans;
    nums.sort((a, b) => a - b); // 排序
    for (let i = 0; i < len ; i++) {
        if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        let L = i+1;
        let R = len-1;
        while(L < R){
            const sum = nums[i] + nums[L] + nums[R];
            if(sum == 0){
                ans.push([nums[i],nums[L],nums[R]]);
                while (L 0) R--; // 和大于0
        }
    }        
    return ans;
};

执行结果：通过
执行用时：160 ms, 在所有 Javascript 提交中击败了 32.62%的用户
内存消耗：47.6 MB, 在所有 Javascript 提交中击败了 89.30% 的用户
通过测试用例： 318 / 318

javascript版本会在测试用例中不通过

[-1,0,1,2,-1,-4,-2,-3,3,0,4]

观察主要是何问题

var threeSum= function(nums) {
    let n = nums.length;
    nums.sort();
    let result = [];

    for(let first=0;first0&&nums[first]==nums[first-1]){
            continue;
        }
        // 对应的指针初始指向数组的最右端
        let third = n-1;
        let target = -nums[first];
        // 枚举第二个数
        for(let second = first+1;secondfirst+1&&nums[second]==nums[second-1]){
                continue;
            }
            // 需要保证b的指针在c指针左侧
            while(secondtarget){
                --third;
            }
            // 如果指针重合，则随着B后续增加
            // 就不会有a+b+c=0并且b 
Java版本无此问题
 
class Solution {
    public List> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List> ans = new ArrayList>();
        // 枚举 a
        for (int first = 0; first < n; ++first) {
            // 需要和上一次枚举的数不相同
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            // c 对应的指针初始指向数组的最右端
            int third = n - 1;
            int target = -nums[first];
            // 枚举 b
            for (int second = first + 1; second < n; ++second) {
                // 需要和上一次枚举的数不相同
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 需要保证 b 的指针在 c 的指针的左侧
                while (second < third && nums[second] + nums[third] > target) {
                    --third;
                }
                // 如果指针重合，随着 b 后续的增加
                // 就不会有满足 a+b+c=0 并且 b list = new ArrayList();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ans.add(list);
                }
            }
        }
        return ans;
    }
}

 
参考 
三数之和