4-3sum

突然想不开做了一道middle难度的题目。。。卡了好久 感觉应该吧easy都刷完再来刷middle

题目

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

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

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

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

解答

双指针法

从左往右

var threeSum = function(nums) {
  nums.sort((a, b) => a - b);
  let result = [];
  if (nums[0] > 0 || nums[nums.length - 1] < 0) {
    return result;
  }
  for (
    let i = 0;
    i < nums.length - 2 && nums[i] + nums[i + 1] + nums[i + 2] <= 0;
    i++
  ) {
    let low = i + 1;
    let high = nums.length - 1;
    while (low < high) {
      const ans = nums[low] + nums[high] + nums[i];
      if (ans === 0) {
        result.push([nums[low], nums[high], nums[i]]);
        while (nums[low] === nums[low + 1]) {
          low++;
        }
        low++;
        while (nums[high] === nums[high - 1]) {
          high--;
        }
        high--;
      } else if (ans < 0) {
        while (nums[low] === nums[low + 1]) {
          low++;
        }
        low++;
      } else if (ans > 0) {
        while (nums[high] === nums[high - 1]) {
          high--;
        }
        high--;
      }
    }
    while (nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return result;
};

Runtime: 164 ms, faster than 80.66% of JavaScript online submissions for 3Sum.

Memory Usage: 46.9 MB, less than 56.45% of JavaScript online submissions for 3Sum.

从右往左

力扣上面一个思路清晰的大佬：

1. 先排序，从小到大，有序数组方便快速过滤，不然时间复杂度就是O(n3)了。

2. 从右到左循环数组，因为最少得3个数，所以最小循环到第3个数就截止。

3. 如果右侧最大的3个连续数字加起来，还比0小，那左边不可能有数字加起来为0了。

4. 如果当前数字和右边的数字一样大，那就是重复数字，直接跳过

5. 如果本次循环中，当前数字加上最左侧的两个数字，和大于0，那么加上其它数字只会更大，所以也直接跳过本次循环

6. 定义两个指针l(左侧指针)、r(右侧指针)，每次循环时，左侧指针从0开始，右侧指针从当前下标i左边第一个数字开始，慢慢让两个指针往中间移动，直到两个指针相撞

   • 当左指针加右指针的和太大时，说明需要更小的值，要把右指针往左移动

   • 当左指针加右指针的和太小时，说明需要更大的值，要把左指针往右移动

   • 如果指针移动后的值和移动前一样大，那就继续移动，直到值不一样了。

   • 当左指针加右指针的和正好时，我们就找到了一组解，这时再同时移动左右指针。因为只移动一个的话，已经有两个数字是固定的了，要算得到解，第3个数字也一定是一样的。

7. 在判断指针相撞的while里，还可以加个条件（在本次循环中，如果最左侧的两个数字之和大于需要的数字，那其它数字之和就更大了，所以可以直接跳过本次循环；如果最右侧的两个数字之和小于需要的数字，同理），进一步过滤多余数据。但是这个条件本身也需要计算，被它过滤掉的计算量也不大，两者相比，不一定哪个更优。实测结果还是不加这个条件稍好一点。

作者：cuidingfeng 链接：https://leetcode-cn.com/problems/two-sum/solution/javascriptpai-xu-shuang-zhi-zhen-pan-duan-by-cuidi/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

var threeSum = function(nums) {
    nums = nums.sort((a, b) => a - b);
    let arr = [];
    for(let i = nums.length-1; i>1 && nums[i] + nums[i-1] + nums[i-2] >= 0; i--){
        if(nums[i] === nums[i+1] || nums[i] + nums[1] + nums[0] > 0) continue;
        const s = 0 - nums[i];
        let l = 0, r = i - 1;
        //while(l<r && nums[l]+nums[l+1]<=s && nums[r]+nums[r-1]>=s){
        while(l<r){
            if(nums[l] + nums[r] > s){
                do{--r}while(nums[r]===nums[r+1])
            }else if(nums[l] + nums[r] < s){
                do{++l}while(nums[l]===nums[l-1])
            }else{
                arr.push([nums[l], nums[r], nums[i]]);
                do{--r}while(nums[r]===nums[r+1]);
                do{++l}while(nums[l]===nums[l-1])
            }
        }
    }
    return arr;
};

Runtime: 152 ms, faster than 95.80% of JavaScript online submissions for3Sum.

Memory Usage: 47.5 MB, less than 22.21% of JavaScript online submissions for 3Sum.

探险过程

双指针法

感觉就是在two sum的双指针下，再多加一个循环

// 原始版本
var threeSum = function(nums) {
  let result = [];
  nums.sort();    // 因为只需要传出元素，不需要下标，因此可以破坏掉原有的数组
  for (let i = 0; i < nums.length - 2; i++) { // 起码留3个数
    let low = i + 1; // 避免和i取到同一个值
    let high = nums.length - 1;
    while (low < high) {
      const ans = nums[low] + nums[high] + nums[i];
      if (ans === 0) {
        result.push([nums[low], nums[high], nums[i]]); // 找到了就推入
        break;
      } else if (ans < 0) {
        low++;
      } else if (ans > 0) {
        high--;
      }
    }
  }
  return result;
};

这个原始版本，内容相同的数组会被保留，也没有处理[0,0,0,0]之类的极端值。 运行的结果是极端值的报错。输入[0,0,0,0]输出了[[0,0,0], [0,0,0]]然而只期望一个全0的数组。

那么怎么让输出的result不再重复呢？

• 一种做法，是像测试代码一样，result整体排序，再每个排序，再转成string塞入set中去重，再把set的值pop出来转成array，再push进result中。

当然这相当复杂。

• 看到另一种思路很厉害。为什么结果会有重复值？即使i，low，high不同，他们指向的元素有可能相同。

  换言之，移动指针的时候检查一下，如果有一样的元素就跳过即可。

因此改进

var threeSum = function(nums) {
  let result = [];
  nums.sort(); // 因为只需要传出元素，不需要下标，因此可以破坏掉原有的数组
  for (let i = 0; i < nums.length - 2; i++) { // 起码留3个数
    let low = i + 1;
    let high = nums.length - 1;
    while (low < high) {
      const ans = nums[low] + nums[high] + nums[i];
      if (ans === 0) {
        result.push([nums[low], nums[high], nums[i]]);
        break;
      } else if (ans < 0) {
        while (nums[low] === nums[low + 1]) {    // 增加跳过
          low++;
        }
      } else if (ans > 0) {
        while (nums[high] === nums[high - 1]) { // 增加跳过
          high--;
        }
      }
    }
    while (nums[i] === nums[i + 1]) {    // i也跳过
      i++;
    }
  }
  return result;
};

这下就进入了死循环……chrome直接卡死。

查了半天，发现第三行sort()之后的nums有点问题，并没有完整排序。

image-20190629192326396

因为-1在前-4在后，导致low的指针一直在-1和-4之间来回打转，形成死循环，因此超出了运行时间，也让我的chrome卡死。

sort() MDN

sort()设计出来，就是为了字符串的排序。输入number会先转换为string，即25大于100，因为开头的2大于1，这显然不对。

而sort()接受一个compareFunction(a, b)，如果返回值小于0，那么a被排到b的前面；大于0则相反；等于0就不变。 因此从小到大的比较函数，可以写为(a, b)=> a-b，从大到小就可以是(a, b)=> b-a

image-20190629190945283

var threeSum = function(nums) {
...
    // 正确排序
  nums.sort((a, b) => a - b);
...
};

结果依然是死循环……

打印其中的过程发现，low的指针一直没有动：

...
        while (low < high) {
      const ans = nums[low] + nums[high] + nums[i];
      console.log("=test=>", nums[i], nums[low], nums[high], ans); // 打印
      console.log("=num=>", i, low, high); // 打印
      if (ans === 0) {
        result.push([nums[low], nums[high], nums[i]]);
        break;
      } else if (ans < 0) {
        while (nums[low] === nums[low + 1]) {
          low++;
        }
      } else if (ans > 0) {
        ...
      }
...

原因是10行到12行，low的指针虽然会跳过相同值，但遇到不同值就不会动了

...
            } else if (ans < 0) {
        while (nums[low] === nums[low + 1]) {
          low++;
        }
        low++;        // 不同值也要变动low指针
      } else if (ans > 0) {
...

结果是wrong answer，因为有遗漏值，输入[-1, 0, 1, 2, -1, -4]只返回一个解[-1, 0, 1]，另一个[-1, -1, 2]没有找到。

是因为在ans===0的时候，push完就直接break了。换言之，找到i的一个解之后就马上放弃该i剩下的其他值。 改咯：

...
if (ans === 0) {
  result.push([nums[low], nums[high], nums[i]]);
  while (nums[low] === nums[low + 1]) { // 两个指针一起移动
    low++;
  }
  low++;
  while (nums[high] === nums[high - 1]) {
    high--;
  }
  high--;
} else if (ans < 0) {
}
...

为啥找到ans之后要两个指针一起移动？因为只移动一个的话，那么就算有值，也只是相同的值。

现在代码更新如下：

var threeSum = function(nums) {
  nums.sort((a, b) => a - b);
  let result = [];
  if (nums[0] > 0 || nums[nums.length - 1] < 0) {
    return result;
  }
  for (
    let i = 0;
    i < nums.length - 2 && nums[i] + nums[i + 1] + nums[i + 2] <= 0; // 判断
    i++
  ) {
    let low = i + 1;
    let high = nums.length - 1;
    while (low < high) {
      const ans = nums[low] + nums[high] + nums[i];
      if (ans === 0) {
        result.push([nums[low], nums[high], nums[i]]);
        while (nums[low] === nums[low + 1]) {
          low++;
        }
        low++;
        while (nums[high] === nums[high - 1]) {
          high--;
        }
        high--;
      } else if (ans < 0) {
        while (nums[low] === nums[low + 1]) {
          low++;
        }
        low++;
      } else if (ans > 0) {
        while (nums[high] === nums[high - 1]) {
          high--;
        }
        high--;
      }
    }
    while (nums[i] === nums[i + 1]) {
      i++;
    }
  }
  return result;
};

Runtime: 160 ms, faster than 86.00% of JavaScript online submissions for 3Sum.

Memory Usage: 47.4 MB, less than 23.60% of JavaScript online submissions for 3Sum.

• for循环的时候多加了一步判断。如果本轮i里面最左边三个加起来，都大于0，那么之后的循环都不必做了，必然都是无解的。

• 刚进入for循环之后也增加了判断。如果本循环内第一个和最后俩相加都小于零，那么接下来的都不用

当然同样的从左往右解法，还有其他的写法：

var threeSum = function (nums) {
  let res = [];
  nums.sort((a, b) => a - b);
  let size = nums.length;
  if (nums[0] <= 0 && nums[size - 1] >= 0) {
    let i = 0;        // 区别1:自定义i
    while (i < size - 2) {
      if (nums[i] > 0) break; // 最左侧大于0，无解 // 区别2:break
      let first = i + 1;
      let last = size - 1;
      while (first < last) {
        if (nums[i] * nums[last] > 0) break; // 三数同符号，无解
        let sum = nums[i] + nums[first] + nums[last];
        if (sum === 0) {
          res.push([nums[i], nums[first], nums[last]]);
        }
        if (sum <= 0) {
          // 负数过小，first右移
          while (nums[first] === nums[++first]) {} // 重复值跳过 //区别3:++
        } else {
          while (nums[last] === nums[--last]) {} // 重复值跳过
        }
      }
      while (nums[i] === nums[++i]) {} // i重复值跳过
    }
  }

  return res;
};

Runtime: 164 ms, faster than 81.45% of JavaScript online submissions for 3Sum.

Memory Usage: 47.1 MB, less than 40.10% of JavaScript online submissions for3Sum.

这种写法和我的写法有三种区别：

• 首先自己定义i，然后通过while自己来控制i的指针。

  这我感觉for来写会更加直观一些

• 其次有break语句。这是说跳出if外面最近的一层循环。就整个循环都跳过。

  还有个和它配套的continue，意思是跳过本轮循环，相当于下面代码都不执行，直接i++执行新的一轮

  这些理解起来都很别扭，感觉可读性不太强就没用了。

• 最后是++写在前面的做法

  i++意味着运算结束后，i=i+1

  ++i意味着先i=i+1，再执行运算

也就是说：

while (nums[low] === nums[++low]) {}

// 相当于
while (nums[low] === nums[low + 1]) {
  low++;
}
low++;

我还是更喜欢下面的写法，感觉更容易理解。++low还要再转一个弯……

不过还是有些情况必须要用上continue。比如在从右往左里面，进入循环后的第五行，有个过滤：

...
    if(nums[i] === nums[i+1] || nums[i] + nums[1] + nums[0] > 0) continue;
...

第一个是过滤掉一样的内容，第二个是过滤掉无解的情况

放在从左往右里面就是这样：

...
        if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
      continue;
    }
...

Runtime: 164 ms, faster than 80.66% of JavaScript online submissions for3Sum.

Memory Usage: 47.6 MB, less than 21.65% of JavaScript online submissions for 3Sum.

但用i++似乎就会有问题，有可能一下子就跳出了for的判断区域

哈希表

试了半天没试出来。。。算了。。

测试代码

/**
 *
 * @param {number[][]} condition：输入的answer
 * @param {number[][]} target：答案
 * @param {string} label：报错标记符
 */

const ensure = (condition, target, label) => {
  if (condition.length !== target.length) {
    wrongMsg(condition, target, label);
    return;
  }
  // 两层数组都排序一下，并转成string，方便对比内容是否一致
  const ansSort = condition.map(e => e.sort().toString()).sort();
  const targetSort = target.map(e => e.sort().toString()).sort();
  for (let i = 0; i < ansSort.length; i++) {
    if (ansSort[i] !== targetSort[i]) {
      // 如果都排序好了，就应该有一样的内容了
      wrongMsg(condition, target, label);
      break;
    }
  }
};