LeeCode problem 1. Two Sum

朱雀 2022-06-01 01:24 166阅读 0赞

### Description ###

--------------------

> Given an array of integers, return indices of the two numbers such  
> that they add up to a specific target.
> 
> You may assume that each input would have exactly one solution, and  
> you may not use the same element twice.

### Example: ###

> Given nums = \[2, 7, 11, 15\], target = 9,  
> Because nums\[0\] + nums\[1\] = 2 + 7 = 9,  
> return \[0, 1\].

### 测试用例 ###

> 输入：3,3 6  
> 输出： 0,1

--------------------

> 输入：2,3,3 5  
> 输出： 0,1  
> 下面代码没有通过这个测试，但是A了。题目说结果是确定的，应该就是不考虑这种情况。

### 思路 ###

1.  先排序，最快O(nlogn)。再左右夹逼。比较暴力。
2.  利用hash表，时间复杂度为O(n)。下面代码是基于第二种方法。

### 代码 ###

vector<int> twoSum(vector<int>& nums, int target) {
            map<int,int> hashMap;
            for(int i = 0; i<nums.size(); i ++) hashMap[nums[i]] = i;
    
            //cout<<hashMap.size()<<endl;
    
            vector<int> ans;
            for(int i = 0; i<nums.size(); i ++){
                const int gap = target - nums[i];
                if(hashMap[gap] > 0){
                    ans.push_back(i);
                    ans.push_back(hashMap[gap]);
                    break;
                }
            }
            return ans;
        }

/* 官方java答案*/
        public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
       }