1. 两数之和

思路

嵌套循环,每一个值与剩下的值相加比较是否满足条件

  1. var twoSum1 = function(nums, target) {
  2.     for (let i = 0; i < nums.length; i++) {
  3.         for (let j = 0; j < nums.length; j++) {
  4.             if (j == i) continue
  5.             let res = (nums[i] + nums[j] === target)
  6.             if (res) return [i, j]
  7.         }
  8.     }
  9. };

优化思路

上述代码假设参数为 [1,2,3], 5

  • 第一次循环, 1去和2,3判断
  • 第二次循环, 2去和1,3判断

这里就能发现,1已经找过2了,所以2是不需要找前面的数的,,只要继续找后面的数即可

所以内部循环不应该从0开始, 而是从i+1开始

  1. for (let i = 0; i < nums.length; i++) {
  2.     for (let j = i + 1; j < nums.length; j++) {
  4.     }
  5. }

最终代码

  1. var twoSum2 = function (nums, target) {
  2.     for (let i = 0; i < nums.length; i++) {
  3.         for (let j = i + 1; j < nums.length; j++) {
  4.             let res = (nums[i] + nums[j] === target)
  5.             if (res) return [i, j]
  6.         }
  7.     }
  8. };

注意: 虽然函数2省了一半循环次数,但提交代码之后,运行时间反而更长了,内存消耗也增加了一点,俗称反向优化…

反向优化(1/1) 完成