力扣第15、53题

15.三数之和

image.png

思路：双指针、暴力三重for

双指针方案：先把数组升序排序，先for循环i=0，i++，然后定义 l、r 左右指针l = i +1 r = 数组长度-1(n-1), 将三个索引的值加起来赋值给tem tem大于0 就r— 小于0就 l++，然后注意查重。

  1. var threeSum = function(nums) {
  2.     if(nums.length < 3){
  3.         return [];
  4.     }
  5.       //从小到大排序
  6.     nums.sort((a,b) => a-b);
  7.     const n = nums.length
  8.     //最小值大于0或者最大值小于0，声明没有有效答案
  9.     if(nums[0] > 0 || nums[n-1] < 0){
  10.         return [];
  11.     } 
  12.     const res = [];
  13.     for(let i =0; i < n; i++){
  14.           //双指针
  15.         let l = i + 1;
  16.         let r = n - 1;
  17.           //如果当前值大于0，和右边的值，所以直接退出
  18.         if(nums[i] > 0){
  19.             return res;
  20.         }
  21.         if(i > 0 && nums[i] === nums[i-1]){
  22.             continue;
  23.         }
  24.         while(l < r){
  25.             let tem = nums[i] + nums[l] + nums[r];
  26.               //值大了右边减小
  27.             if(tem > 0){
  28.                 r--;
  29.             }
  30.               //值笑了左边增大
  31.             if(tem < 0){
  32.                 l++;
  33.             }
  34.             if(tem === 0){
  35.                 res.push([nums[i],nums[l],nums[r]])
  36.                   //跳过重复
  37.                 while(l < r && nums[l] === nums[l+1]){
  38.                     l++;
  39.                 }
  40.                   //同上
  41.                 while(l < r && nums[r] === nums[r-1]){
  42.                     r--;
  43.                 }
  44.                 l++;
  45.                 r--;
  46.             }
  47.         }
  48.     }
  49.     return res;
  50. };

53.最大子序和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
image.png

思路：动态规划

  • 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
  • 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
  • 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
  • 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
  • 时间复杂度：O(n)O(n)

解释：应该这么想：

  1. 假如全是负数，那就是找最大值即可，因为负数肯定越加越大。
  2. 如果有正数，则肯定从正数开始计算和，不然前面有负值，和肯定变小了，所以从正数开始。
  3. 当和小于零时，这个区间就告一段落了，然后从下一个正数重新开始计算(也就是又回到 2 了)。而 dp 也就体现在这个地方。
    1. var maxSubArray = function(nums) {
    2.  let ans = nums[0];
    3.  let sum = 0;
    4.  for(const num of nums) {
    5.      if(sum > 0) {
    6.          sum += num;
    7.      } else {
    8.          sum = num;
    9.      }
    10.      ans = Math.max(ans, sum);
    11.  }
    12.  return ans;
    13. };