Data structure

Array

1. 两数之和

date：22.2.22

Quesion

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

Example

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

Hint

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

AC code1

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        int i, j;
        for(i = 0; i < nums.size()-1; i++){
            for(j = i + 1; j < nums.size(); j++){
                if (nums[i] + nums[j] == target){
                    return {i, j};  
                }
            }
        }
        return {}; /* no answer should return null */
    };
};

• 暴力匹配就可以了，注意j的变化在i之后。但O(n)为O(n^2)，太慢了。
• knowlegle：size()返回一个vector得长度

AC code2

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        /* array map element to index */
        map array_element_index;
        /* answer has two index */
        vector answer(2, 0);
        for (int i = 0; i < nums.size(); i++)
            array_element_index.insert(map::value_type(nums[i], i));
        for (int i = 0; i< nums.size(); i++){
            /* use count() find the element and can't be itself */
            if(array_element_index.count(target - nums[i]) && (array_element_index[target - nums[i]] != i)){
                answer[0] = i;
                answer[1] = array_element_index[target - nums[i]];
                break;
            }
        }
        return answer;
    };
};

• 使用hash表，将原来的nums反过来映射一遍，没错，我们恰好是将数组中的元素（element）和索引（index）反过来了，在array_element_index中key是element，value是index

• 使用count()能非常巧妙的找出匹配的element，但注意不能是本身

  • 例如nums = [3, 2, 4], target = 6，如果是本身的话3+3 = 6，显然不符合题意

• knowlegle

  • vector answer(2, 0);是创建一个有两个初始数值为0的vector
  • count()是计算某个key出现的次数，如果没找到就返回0