1. Two Sum

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

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

暴力法

遍历两个数组，在index不一致的情况下找出合为target的组合。

很明显，时间复杂度是O(n2)，空间复杂度是O(1).

在时间复杂度上来说是非常昂贵的。

pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut ret = [].to_vec();
    for (index1, v1) in nums.iter().enumerate() {
        for (index2, v2) in nums.iter().enumerate() {
            if (v1 + v2) == target && index1 != index2 {
                ret.push(index1 as i32);
                ret.push(index2 as i32);
                return ret;
            }
        }
    }
    ret
}

暴力法的优化

在上述的暴力法中，有很多重复的计算。

对于数组中的某个元素，他和数组中的其他元素的match如下：

不用每次从头比对，从本次比对元素的那个位置开始就可以：

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let mut ret = [].to_vec();
    for (index1, v1) in nums.iter().enumerate() {
        for (index2, v2) in nums.iter().enumerate().filter(|&(i, _)| i > index1) {
            if (v1 + v2) == target {
                ret.push(index1 as i32);
                ret.push(index2 as i32);
                return ret;
            }
        }
    }
    ret
}

当然，时间复杂度仍然是O(n2)，并没有本质上的改变。

哈希表

因为有两个nested for loop，所以时间复杂度才会这么高。

那么要降低时间复杂度，最直接的思路就是 loop => hash，理想状态下的hashmap的时间复杂度是O(1)。

• key: 值
• value: 值对应的数组下标

fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
    use std::collections::HashMap;
    let mut kv = HashMap::<i32, usize>::new();
    for (index1, value) in nums.iter().enumerate() {
        let index2 = kv.get(&(target - value));
        match index2 {
            Some(i) => return [(*i) as i32, index1 as i32].to_vec(),
            None => {
                kv.insert(*value, index1);
            },
        }
    }
    [].to_vec()
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const map = {};
    for (let i = 0; i < nums.length; i++) {
        if (map[target - nums[i]] !== undefined) return [i, map[target - nums[i]]];
        else map[nums[i]] = i;
    }
};

时间复杂度是O(n), 空间复杂度也是O(n).

双指针

看到两个nested loop，其实很容易联想到用双指针去优化。

/**
 * 双指针
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const arr = [...nums].sort((a, b) => a - b);
  let p1 = 0;
  let p2 = arr.length - 1;
  while (p1 < p2) {
    const v = arr[p1] + arr[p2];
    if (v > target) {
      p2--;
    } else if (v < target) {
      p1++;
    } else {
      const i1 = nums.findIndex((v) => v === arr[p1]);
      const i2 = nums.findIndex((v, i) => i !== i1 && v === arr[p2]);
      return [i1, i2];
    }
  }
};

时间复杂度是O(nlogn), 空间复杂度也是O(n).

总结

在优化时间复杂度的时候，针对数组，可以优先考虑利用hashmap去提升便利效率，利用空间换时间。