LeetCode 之两数之和 + 三数之和 + 四数之和

冷不防 2022-09-12 02:53 238阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5Y-q54uX_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

### [1. 两数之和][1.] ###

var twoSum = function(nums, target) { 
      let map = new Map()
    
      for (let i = 0; i < nums.length; i++) { 
          let k = target - nums[i]
          if (map.has(k)) { 
              return [map.get(k), i]
          }
          map.set(nums[i], i)
      }
      return []
    }

### [15. 三数之和][15.] ###

var threeSum = function(nums) { 
        if(!nums || nums.length < 3) return []
        let result = [], second, last
        // 排序
        nums.sort((a, b) => a - b) 
        for (let i = 0; i < nums.length ; i++) { 
            if(nums[i] > 0) break
            // 去重
            if(i > 0 && nums[i] === nums[i-1]) continue
            second = i + 1
            last = nums.length - 1
            while(second < last){ 
                const sum = nums[i] + nums[second] + nums[last]
                if(!sum){ 
                    // sum 为 0
                    result.push([nums[i], nums[second], nums[last]])
                    // 去重
                    while (second<last && nums[second] === nums[second+1]) second++ 
                    while (second<last && nums[last] === nums[last-1]) last--
                    second ++
                    last --
                }
                else if (sum < 0) second ++
                else if (sum > 0) last --
            }
        }        
        return result
    };

### [18. 四数之和][18.] ###

var fourSum = function(nums, target) { 
      var res = [];
      var len = nums.length;
      if (nums == null || len < 4) return res;
      nums.sort((a, b) => a - b);
      for (let i = 0; i < len - 3; i++) { 
        // 去重(如果下一个固定数和前一个相等,后边会出现重复结果)
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        //计算当前的最小值，如果最小值都比target大，不用再继续计算了
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
        //计算当前最大值，如果最大值都比target小，不用再继续计算了
        if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target)
          continue;
        // 确定第二个指针的位置
        for (let j = i + 1; j < len - 2; j++) { 
          // 去重
          if (j > i + 1 && nums[j] == nums[j - 1]) continue;
          // 定义第三/四个指针
          let L = j + 1;
          let R = len - 1;
          //计算当前的最小值，如果最小值都比target大，不用再继续计算了
          let min = nums[i] + nums[j] + nums[L] + nums[L + 1];
          if (min > target) continue;
          //计算当前最大值，如果最大值都比target小，不用再继续计算了
          let max = nums[i] + nums[j] + nums[R] + nums[R - 1];
          if (max < target) continue;
          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]]);
            }
            if (sum < target) { 
              while (nums[L] === nums[++L]);
            } else { 
              while (nums[R] === nums[--R]);
            }
          }
        }
      }
      return res;
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5Y-q54uX_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220828/6079258f69f2455dbe9447860055be49.png
[1.]: https://leetcode-cn.com/problems/two-sum/
[15.]: https://leetcode-cn.com/problems/3sum/
[18.]: https://leetcode-cn.com/problems/4sum/

发表评论取消回复

表情：

评论列表（有 0 条评论，238人围观）

还没有评论，来说两句吧...

相关阅读

相关两数之和、三数之和、四数之和、K数之和

数之和、三数之和、四数之和和K数之和是最近听室友提起的几道有意思的基础题，可以说是把双指针运用的淋漓尽致。（K数之和其实是一个动态规划的题，此处因为满足`*数之和`的的结...

淡淡的烟草味﹌/ 2024年04月17日 19:48/ 0 赞/ 96 阅读

相关 leetcode 1两数之和，leetcode15三数之和，leetcode18四数之和,leetcode 454四数相加II

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能

秒速五厘米/ 2023年06月16日 02:22/ 0 赞/ 28 阅读

相关算法笔记-两数之和、三数之和、四数之和（LeetCode)

两数之和 1.两数之和题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假

青旅半醒/ 2023年02月14日 02:29/ 0 赞/ 25 阅读

相关【LeetCode】两数之和、三数之和、四数之和系列

文章目录两数之和★ 三数之和★★ 四数之和★★ 四数相加Ⅱ★★

r囧r小猫/ 2022年12月26日 04:49/ 0 赞/ 218 阅读

相关 LeetCode 之两数之和 + 三数之和 + 四数之和

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5reY5reY5piv5

冷不防/ 2022年09月12日 02:53/ 0 赞/ 239 阅读

相关 LeetCode之两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例: 给定 nums = [2,

╰+哭是因爲堅強的太久メ/ 2022年05月27日 12:05/ 0 赞/ 206 阅读

相关 leetcode 两数之和、三数之和、最接近的三数之和、四数之和

两数之和题目链接：[两数之和][Link 1] 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重

缺乏、安全感/ 2022年05月25日 06:46/ 0 赞/ 345 阅读

相关 leetcode题解之两数之和 && 三数之和

1.两数之和给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例: 给定 num

﹏ヽ暗。殇╰゛Y/ 2022年05月15日 01:47/ 0 赞/ 241 阅读

相关 LeetCode 两数之和、三数之和

1. 两数之和给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。你可以假设每种输入只会对应一个答案。但是，你不能重复

旧城等待，/ 2022年04月13日 05:42/ 0 赞/ 288 阅读

相关两数之和LeetCode

给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是

男娘i/ 2022年01月12日 08:47/ 0 赞/ 278 阅读