阅读 667

分分钟搞定【n数之和】算法面试题

一、前言

不知不觉,近两年大厂将算法作为衡量候选人的重要指标。如果算法不过关,很多大厂会将你拒之门外。如果你想提升自己的基本功或今后准备进入大厂,那么开始觉悟准备好头秃吧 :),让我们从这篇算法题开始。

刷过Leet-code(力扣)的同学知道,两数之和是开启算法的第一题,比较简单。但遇到三数之和、四数之和、n数之和你是同样否有思路呢?

其实这类题的解题都有共性,本文将教大家从中寻找规律,让麻麻以后再也不用担心你的学习。

本文我只举例两类的算法,其他方法暂不介绍,这样方便大家学习和记忆。通过本文,你将学会:

  • 暴力算法
  • 排序+双指针算法
  • 求解n数之和类型题

建议:先码后看、自己跑一跑文中代码

二、暴力算法

【题目1】两数之和(难度:简单)

两数之和:leetcode-cn.com/problems/tw…

给定一个整数数组 nums 和一个目标值target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
复制代码

方法:

最简单的也就是 暴力算法

var twoSum = function(nums, target) {
    for(let i = 0 ; i<nums.length -1; i++) {
        for(let j = i+1; j < nums.length; j++) {
            if(nums[i]+nums[j] === target) {
                return [i, j];
            }
        }
    }
};
复制代码

使用两层循环,外层循环计算当前元素与 target 之间的差值,内层循环寻找该差值,若找到该差值,则返回两个元素的下标。

时间复杂度:O(n^2)。

好,上面我们使用了暴力算法来算出了两数之和。 那么接下来我们来类推下,如何计算三数之和、四数之和呢?接着往下看。

【题目2】三数之和(难度:中等)

三数之和:leetcode-cn.com/problems/3s…

给你一个包含 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) {
      let res = [];
      nums.sort((a, b) => a-b);
      for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
          for (let k = j + 1; k < nums.length; k++) {
            if (nums[i] + nums[j] + nums[k] === 0) {
              res.push([nums[i], nums[j], nums[k]])
            }
          }
        }
      }
      return res;
    }
复制代码

上面我们使用三层循环,时间复杂度:O(n^3)。我们跑一下结果得到如下:

嗯,是的,这还不对,我们需要对结果进行去重,这也是三数之和和两数之和同样使用暴力算法中不一样的地方。可能这时候你会想到直接将结果像下面这么处理一下不就行了嘛。

Array.from(new Set(res))
复制代码

但这是二维的数组,算是去重上的一个小难点。所以这里我们利用 hash 方法来去重,小白可以先来简单了解下去重:

// 初级版本(一维)
function unique(arr) {
    let tempObj = new Set();
    let res = [];
    for(let i =0;i<arr.length; i++) {
        if(!tempObj.has(arr[i])) {
            res.push(arr[i]);
            tempObj.add(arr[i]);
        }
    }
    return res;
}

uinque([1,1,2]); // [1, 2]

-----------分割线

// 高级版本(多维)
function unique(arr) {
    let res = [];
    let tempObj = new Set();
    for(let i =0;i<arr.length; i++) {
        // 每个元素转为字符串
        let tempStr = arr[i] + '';
        if(!tempObj.has(tempStr)) {
            res.push(arr[i]);
            tempObj.add(tempStr);
        }
    }
    return res;
}
// 试一下:
unique([[1,2],[1,2], 2,3]); // [[1,2], 2, 3]
unique([[1,[1,2]],[1,[1,2]], 2,3]); // [[1,[1,2]], 2, 3] 

// 嗯,ojbk!
复制代码

ok fine,接下来我们继续!用 hash 去重来处理前面的三数和的去重:

// 原始版本
function unique(arr) {
    let res = [];
    let tempObj = new Set();
    for(let i =0;i<arr.length; i++) {
        // 每个元素转为字符串
        let tempStr = arr[i] + '';
        if(!tempObj.has(tempStr)) {
            res.push(arr[i]);
            tempObj.add(tempStr);
        }
    }
    return res;
}

var threeSum = function(nums) {
      let res = [];
      nums.sort((a, b) => a-b);
      for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
          for (let k = j + 1; k < nums.length; k++) {
            if (nums[i] + nums[j] + nums[k] === 0) {
              res.push([nums[i], nums[j], nums[k]])
            }
          }
        }
      }
      
      return unique(res);
    }

-------------------- 分割线
// 将上面去重方法合成下面可能会显得你更“高级前端开发”
var threeSum = function(nums) {
      let res = [];
+     let tempObj = new Set();
      nums.sort((a, b) => a-b);
      for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
          for (let k = j + 1; k < nums.length; k++) {
            if(nums[i]+nums[j]+nums[k] === 0) {
+               let tempRes = [nums[i] + nums[j] + nums[k]];
+               let tempStr = tempRes + '';
+               if (!tempObj.has(temStr)) {
+                 res.push(tempRes);
+                 tempObj.add(tempStr);
+               }
            }
          }
        }
      }
      return res;
    }
复制代码

well,现在我们完成了三数相加的暴力算法! 接下来我们来以此类推完成一道四数之和。

【题目3】四数之和(难度:中等)

四数之和:leetcode-cn.com/problems/4s…

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

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

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]。
复制代码

方法:

没有什么是暴力解不开的 :),先不管去重,先拿到结果:

var fourSum = function(nums, target) {
      let res = [];
      nums.sort((a, b) => a-b);
      for (let i = 0; i < nums.length - 3; i++) {
        for (let j = i + 1; j < nums.length - 2; j++) {
          for (let k = j + 1; k < nums.length - 1; k++) {
            for(let l = k + 1; l < nums.length; l++){
                if(nums[i]+nums[j]+nums[k]+nums[l] === target) {
                    res.push([nums[i], nums[j], nums[k], nums[l]]);
                }
            }
          }
        }
      }
      return res;
    }
复制代码

接下来,再去去重:

// 去重方法
function unique(arr) {
    let res = [];
    let tempObj = new Set();
    for(let i =0;i<arr.length; i++) {
        // 每个元素转为字符串
        let tempStr = arr[i] + '';
        if(!tempObj.has(tempStr)) {
            res.push(arr[i]);
            tempObj.add(tempStr);
        }
    }
    return res;
}

var fourSum = function(nums, target) {
      let res = [];
      nums.sort((a, b) => a-b);
      for (let i = 0; i < nums.length - 3; i++) {
        for (let j = i + 1; j < nums.length - 2; j++) {
          for (let k = j + 1; k < nums.length - 1; k++) {
            for(let l = k + 1; l < nums.length; l++){
                if(nums[i]+nums[j]+nums[k]+nums[l] === target) {
                    res.push([nums[i], nums[j], nums[k], nums[l]]);
                }
            }
          }
        }
      }
+      return unique(res);
    }
复制代码

没有什么是暴力算法解不开的,什么?你说超时了!先不管,反正这题我算是会做了。

就这?太low了,那我们下面来讲讲“高级开发”的解法吧。

三、排序+双指针

知识小讲堂:什么是指针?

凡是数组的题目,大部分都是利用双指针去解决问题。

双指针,指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个相同方向(快慢指针)或者相反方向(对撞指针)的指针进行扫描,从而达到相应的目的。

换言之,双指针法充分使用了数组有序这一特征,从而在某些情况下能够简化一些运算。

1、对撞指针,是指在有序数组中,将指向最左侧的索引定义为左指针(left),最右侧的定义为右指针(right),然后从两头向中间进行数组遍历。

对撞数组适用于有序数组,也就是说当你遇到题目给定有序数组时,应该第一时间想到用对撞指针解题。

快慢指针,也是双指针,但是两个指针从同一侧开始遍历数组,将这两个指针分别定义为快指针(fast)和慢指针(slow),两个指针以不同的策略移动,直到两个指针的值相等(或其他特殊条件)为止,如fast每次增长两个,slow每次增长一个。

先大概了解下什么是指针,如果感到模糊,没关系,做几道题就会啦!

从最简单的题开始。

【题目1】两数之和(难度:简单)

还是这道简单的题目:

两数之和:leetcode-cn.com/problems/tw…

给定一个整数数组 nums 和一个目标值target,请你在该数组中找出和为目标值的那 两个 整数,并返回 他们的数组下标 满足条件的数组。(由于这题太简单,为了学习双指针的使用,此处我们将题目稍作修改)

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

满足要求的数组为:
[2,7]
复制代码

方法:

解题思路: 先来心中默念3遍这句话:

凡是数组的题目,基本上都是利用双指针去解决问题!

凡是数组的题目,基本上都是利用双指针去解决问题!

凡是数组的题目,基本上都是利用双指针去解决问题!

没错,这道题就是使用双指针!一个指针指向值较小的元素,一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历,指向较大元素的指针从尾向头遍历。

如上图,左边就是左指针,右边是右指针。

  • 如果两个指针指向元素的和 sum == target,那么得到要求的结果;
  • 如果 sum > target,移动较大的元素,使 sum 变小一些;
  • 如果 sum < target,移动较小的元素,使 sum 变大一些。

数组中的元素最多遍历一次,时间复杂度为 O(N)。只使用了两个额外变量,空间复杂度为 O(1)。

var twoSum = function(nums, target) {
    let res = [];
    nums.sort((a, b) => a - b); // 让数组成为有序排序
    
    let L = 0; //  定义左指针
    let R = nums.length - 1; // 定义右指针
    
    while(L < R) {
        const sum = nums[L] + nums[R];
        if(sum === target) {
            res.push(nums[L]);
            res.push(nums[R]);
            break;
        } else if(sum > target) {
            R--;
        } else if(sum < target) {
            L--;
        }
    }
    return res;
};

twoSum([3, 1, 7], 8);   // [1, 7]
复制代码

OK,是不是很好理解。接下来继续。

【题目2】三数之和(难度:中等)

三数之和:leetcode-cn.com/problems/3s…

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

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

示例:

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

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
复制代码

方法:

还是这句话,心中默念:凡是数组的题目,基本都是利用双指针去解决问题!

1、拿到原数组:

2、排序:

nums.sort((a, b) => a - b);
复制代码

3、设置左右指针:

for(let i = 0;i < len; i++) {
          
    // 设置左右指针
    let L = i + 1;
    let R = len - 1;
    
}
复制代码

4、从左往右遍历,将nums[i]设置为第一个元素,L为左侧第一个元素,R为当前数组右侧的第一个元素 5、比较 sum(nums[i] + nums[L] + nums[R])和 target 的大小

  • 如果sum < 0,左指针往右移
  • 如果sum > 0,右指针往左移

代码如下:

var threeSum = function (nums) {
      let res = [];
      if(nums === null && nums.length < 3) return res;
      let len = nums.length;
      
      nums.sort((a, b) => a - b); // 老样子,要使用双指针,先成为有序数组

      for(let i = 0;i < len; i++) {
          if(nums[i] > 0) break;
          
          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) {
                res.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--;
            }
            else if(sum < 0) L++; 
            else if(sum > 0) R--;
          }
      }
      return res;
    }
复制代码

这类问题其实就是这样,掌握一个,其他的都是类似解法。需要注意的就是去重。 从上面我们我们可以类推到四数之和,接着往下看!

【题目3】四数之和(难度:中等)

四数之和:leetcode-cn.com/problems/4s…

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

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

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]。
复制代码

方法:

排序+双指针

var fourSum = function (nums, target) {
    let res = [];
    let len = nums.length;
    
    // 关键1:排序
    nums.sort((a, b) => a-b);

    if(len < 4) return res;
    
    for(let i = 0; i<len-3; i++){
        // 关键点2:去重
        if(i > 0 && nums[i] === nums[i-1]) continue;

        for(let j = i+1; j<len-2; j++){
            // 关键点5:去重
            if(j > i+1 && nums[j] === nums[j-1]) continue;
            
            let L = j + 1; // 双指针,最左边的
            let R = len - 1; // 双指针,最右边的

            while(L<R) {
                let sum = nums[i]+nums[j]+nums[L]+nums[R];

                if(sum === target) {
                    res.push([nums[i], nums[j], nums[L], nums[R]]);
                    while(nums[L] === nums[L+1]) L++; // 去重
                    while(nums[R] === nums[R-1]) R--;// 去重
                    L++;
                    R--;
                } else if(sum > target) {
                    R--;
                } else if(sum < target) {
                    L++;
                }
            }
        }
    }
    return res;
}
复制代码

四、总结

关键点:排序、设置左右指针、去重。 这类题目就是这样,掌握一个其他的都是类推,大家刷算法的时候也可以按照类型来,质量大于数量。

以上。