【Day 19 】2024-04-26 - 两数之和

[azl397985856]

两数之和

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/two-sum

前置知识

• 哈希表

  题目描述

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[smallppgirl]

思路： 哈希表 ， 依次把元素 加入哈希表， 直到找到正确结果

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n_dict = {}
        for i in range(len(nums)):
            if target - nums[i] in n_dict:
                return [n_dict[target - nums[i]], i]
            n_dict[nums[i]] = i
        return []

时间复杂 O(n) 遍历所有元素 空间复杂 O(n) 哈希表最大 n 个值

[zhiyuanpeng]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        can = {}
        for i, val in enumerate(nums):
            if val in can:
                return [can[val], i]
            else:
                can[target-val] = i

Time O(N) space O(N)

[CathyShang]

• 哈希表 unordered_map<int, int>
• 遍历数组，将target-nums[i]作为key，i作为value存入哈希表
• 判断当前nums[i] 是否为key值，若是则它的搭档索引已经存入哈希表，返回{i, hashmap[nums[i]]}

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;
        int n = nums.size();

        for(int i=0;i<n;i++){
            auto it = hashmap.find(nums[i]);
            if(it != hashmap.end()){
                return {hashmap[nums[i]],i};
            }
            hashmap[target-nums[i]] = i;
        }
        return {};

    }
};

• Time $O(N)$
• Space $O(N)$

[atom-set]

思路

• 先对数组进行排序
• 收尾进行往中间走，进行判断两数之和
• 拿到数字后再去原数组取下标

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  var sortNums = [...nums].sort((a, b) => (a - b > 0 ? 1 : -1));

  var mid = Math.floor(nums.length / 2);
  var left = 0;
  var right = nums.length - 1;

  while (sortNums[left] + sortNums[right] !== target) {
    if (sortNums[left] + sortNums[right] > target) {
      right--;
    } else if (sortNums[left] + sortNums[right] < target) {
      left++;
    }
    if (right < left) {
      return null;
    }
  }

  var leftPos = -1;
  var rightPos = -1;

  for (var i = 0; i < nums.length; i++) {
    if (nums[i] === sortNums[left] && leftPos === -1) {
      leftPos = i;
      continue;
    }
    if (nums[i] === sortNums[right] && rightPos === -1) {
      rightPos = i;
    }
  }
  return [leftPos, rightPos];
};

复杂度分析

时间复杂度取决于数字排序，空间复杂度使用了临时数组存在

• 时间复杂度：O(N^2)
• 空间复杂度：O(N)

[rao-qianlin]

思路

两次遍历，遇到满足条件的两个元素，直接返回下标结果。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] re = new int[2];
        for(int i=0; i< nums.length; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[i]+nums[j]==target){
                    re[0]=i;
                    re[1]=j;
                    return re;
                }
            }
        }
        return re;
    }
}

复杂度

时间$ O(N^2)$ 空间 $ O(1)$

[wwz223]

思路

遍历数组，将数组值作为下标，数组下标作为值保存在hash数组中，值的数据结构是数组，遍历的过程中获取当前值与target的差，在已存在的hash数组中进行获取，如果没有该值，则循环继续，如果该值存在，则放回对应的两个下标，值的数据结构为数组，目的是解决数组中有两个相同值的问题

代码

var twoSum = function (nums, target) {
    let hash = []
    let res = []
    for (let i = 0; i < nums.length; i++) {
        const val = nums[i]
        if (hash[val] !== undefined) {
            hash[val].push(i)
        } else {
            hash[val] = [i]
        }
        const num = target - val
        if (hash[num] === undefined || (hash[num].length === 1 && hash[num][0] === i)) {
            continue
        }
        if (num === val) {
            res = hash[num]
            break
        } else {
            res = [hash[num], i]
            break
        }
    }
    return res
};  

复杂度

时间复杂度：O(N) 只需要一次循环 空间复杂度：O(N) 取决于nums数组长度

[lxy1108]

思路

采用空间换时间的思路，维护哈希表记录数组中值对应的索引，这样一次遍历就可以检查是否可以构成target

python3代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = dict()
        for i, num in enumerate(nums):
            if target - num in num_dict:
                return [num_dict[target - num], i]
            num_dict[num] = i
        return []

复杂度分析

时间复杂度o(n) 只需要遍历一次数组

空间复杂度o(n) 哈希表的空间开销最差情况与数组大小一致

[xil324]

var twoSum = function(nums, target) { const numberMap = {}; for(let i = 0; i < nums.length; i++) { const need = target - nums[i]; if(need in numberMap) { return [i, numberMap[need]] } else{ numberMap[nums[i]] =i; } } };

[hillsonziqiu]

思路

使用map的能力，将nums数组转换成为key是nums值value是index的map，然后遍历target减去nums中的每一位，如果在map中，那么再判断是不是value和当前下标相同，如果不同则退出循环，返回当前下标和map中对应的下标。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    const numsMap = new Map();
    for (let i = 0; i < nums.length; i++) {
        const item = nums[i];
        numsMap.set(item, i);
    }
    let result;
    for (let i = 0; i < nums.length; i++) {
        const item = nums[i];
        const computedNum = target - item;
        if (numsMap.get(computedNum) !== undefined) {
            if (numsMap.get(computedNum) === i) {
                continue;
            }
            result = [i, numsMap.get(computedNum)]
            break;
        }
    }
    return result;
};

复杂度分析

时间复杂度：O(n) 最多2次循环 2n； 空间复杂度：O(n)

[Dtjk]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int>res;
        for(int i = 0; i < (nums.size() - 1); i++){
            for(int j = i + 1; j < nums.size(); j++){
                if(target == (nums[i] + nums[j])){
                    res.push_back(i);
                    res.push_back(j);
                    break;
                }
            }
        }
        return res;
    }
};

[GReyQT]

题解思路：

（1）双层遍历查找

代码：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        for(int i = 0; i < nums.size(); ++i)
        {
            for(int j = i+1; j < nums.size(); ++j)
            {
                if(nums[i] + nums[j] == target)
                {
                    res.push_back(i);
                    res.push_back(j);
                }
            }
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(n^2)
• 空间复杂度： O(n)

[YANGLimbo]

思路 就正常的两个for循环。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for(int i = 0; i<n;i++){
            for(int j = i+1; j < n; j ++){
                if(nums[i] + nums[j] == target){
                    return vector<int>({i,j});
                }
            }
        }
        return vector<int>();
    }
};