刷Leetcode第一天

題號1盆犁、兩數(shù)之和

題目

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.

雖然這次寒假刷題的主要目的是熟悉C++語法，但是我還是情不自禁用了Java（-_-||
先上Java代碼：

public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        outterloop:for (int i = 0;i < nums.length-1;i++){
            for(int j = i +1 ; j < nums.length;j++){
                if (nums[i] + nums[j] == target){
                    res[0] = i;
                    res[1] = j;
                    break outterloop;
                }
            }
        }
        return res;

思路十分簡單，就是暴力搜索然痊，時間復雜度為O(n²)犀填，空間復雜度為O(1)决侈。

于是我去看了LeetCode的官方題解

方法二：兩遍哈希表

思路是建立一個哈希表，索引是數(shù)據(jù)的下標尖昏，然后在表內(nèi)查找對每個元素查找表內(nèi)對應元素target - nums[i] 是否存在。建立哈希表需要O(n),查找也需要O(n)构资，空間復雜度則是O(n)抽诉。

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

作者：LeetCode
鏈接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/

至此，時間復雜度已經(jīng)充分優(yōu)化到O(n)了吐绵，但是創(chuàng)建和搜索一共需要n~2n的時間迹淌，還可以繼續(xù)優(yōu)化一點，那就是一邊創(chuàng)建的同時搜索該元素有無對應元素己单。

方法三：一遍哈希表

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");
    }

作者：LeetCode
鏈接：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
來源：力扣（LeetCode）
著作權(quán)歸作者所有唉窃。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處纹笼。