1.两数之和

链接：1.两数之和
难度：Easy
标签：数组、哈希表
简介：给定一个整数数组 nums  和一个目标值 target，请你在该数组中找出和为目标值的那   两个   整数，并返回他们的数组下标。

题解 1 - python

• 编辑时间：2023-01-21
• 执行用时：32ms
• 内存消耗：16MB
• 编程语言：python
• 解法介绍：哈希。

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

题解 2 - javascript

• 编辑时间：2019-09-15
• 执行用时：232ms
• 内存消耗：34.8MB
• 编程语言：javascript
• 解法介绍：获取第一个 num 值后，用 target 减去求出对应值，使用 indexOf 判断该对应值是否在数组里。

var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    num1 = nums[i];
    num2 = target - nums[i];
    result = nums.indexOf(num2);
    if (result > -1 && result !== i) {
      return [i, result];
    }
  }
};

题解 3 - typescript

• 编辑时间：2021-07-22
• 执行用时：84ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：二分查找。

function twoSum(nums: number[], target: number): number[] {
  const list = new Array(nums.length)
    .fill(0)
    .map((_, i) => i)
    .sort((a, b) => nums[a] - nums[b]);
  for (let i = 0; i < nums.length; i++) {
    const num = nums[list[i]];
    const i2 = search(target - num, i + 1);
    if (i2 !== -1) return [list[i], list[i2]];
  }
  return [];
  function search(target: number, l: number): number {
    let r = nums.length - 1;
    while (l <= r) {
      const mid = (l + r) >> 1;
      const midNum = nums[list[mid]];
      if (midNum < target) l = mid + 1;
      else if (midNum > target) r = mid - 1;
      else return mid;
    }
    return -1;
  }
}

题解 4 - cpp

• 编辑时间：2021-12-20
• 执行用时：4ms
• 内存消耗：10.4MB
• 编程语言：cpp
• 解法介绍：哈希存储。

class Solution {
   public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> m;
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            int num = nums[i];
            if (m.count(target - num)) {
                ans.push_back(m[target - num]);
                ans.push_back(i);
                return ans;
            } else {
                m[num] = i;
            }
        }
        return ans;
    }
};

题解 5 - typescript

• 编辑时间：2020-10-03
• 执行用时：84ms
• 内存消耗：40.2MB
• 编程语言：typescript
• 解法介绍：哈希储存下一值。

function twoSum(nums: number[], target: number): number[] {
  const cache = new Map<number, number>();
  for (let i = 0, l = nums.length; i < l; i++) {
    const num = nums[i];
    const nextI = cache.get(num);
    if (nextI !== undefined) return [nextI, i];
    const nextNum = target - num;
    cache.set(nextNum, i);
  }
  return [];
}

题解 6 - javascript

• 编辑时间：2019-09-15
• 执行用时：68ms
• 内存消耗：35.2MB
• 编程语言：javascript
• 解法介绍：获取第一个 num 值后，判断该值是否存在 map 表中，若存在则说明有匹配项直接返回，若不存在则储存。

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

题解 7 - c

• 编辑时间：2021-11-30
• 执行用时：8ms
• 内存消耗：6.3MB
• 编程语言：c
• 解法介绍：创建下标数组后排序后二分。

int *gnums;
int comp(const void *a, const void *b){
    return gnums[(*(int *)a)] - gnums[(*(int *)b)];
}
int bs(int *arr, int numsSize, int start, int num){
    int m, l = start, r = numsSize - 1;
    if (gnums[arr[l]] > num || gnums[arr[r]] < num) return -1;
    while (l < r) {
        m = (l + r) >> 1;
        if (gnums[arr[m]] == num) {
            l = m;
            break;
        }
        if (gnums[arr[m]] > num) r = m - 1;
        else l = m + 1;
    }
    return gnums[arr[l]] == num ? l : -1;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    gnums = nums;
    *returnSize = 2;
    int *ans = (int *)malloc(sizeof(int) * 2);
    int arr[numsSize];
    for(int i = 0; i < numsSize; i++) arr[i] = i;
    qsort(arr, numsSize, sizeof(int), comp);
    for(int i = 0; i < numsSize; i++) {
        int num1 = nums[arr[i]], num2 = target - num1;
        int num2idx = bs(arr, numsSize, i + 1, num2);
        if (num2idx == -1) continue;
        if (arr[i] > num2idx) {
            ans[0] = arr[num2idx];
            ans[1] = arr[i];
        } else {
            ans[1] = arr[num2idx];
            ans[0] = arr[i];
        }
        break;
    }
    return ans;
}

题解 8 - rust

• 编辑时间：2023-07-01
• 内存消耗：2.4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut m = std::collections::HashMap::<i32, usize>::new();
        for i in 0..nums.len() {
            match m.get_mut(&(target - nums[i])) {
                Some(prev) => return vec![*prev as i32, i as i32],
                None => {
                    m.insert(nums[i], i);
                }
            }
        }
        vec![]
    }
}