Leetcode-problem1

題目描述

給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，你不能重復(fù)利用這個數(shù)組中同樣的元素。
示例:

**給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1] **

1.暴力法

遍歷每個元素，查找符合結(jié)果的值

public int[] twoSum(int[] nums, int target) {
        public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {                     //設(shè)置循環(huán)對數(shù)組進(jìn)行遍歷，第一次循環(huán)確定一個家數(shù)
            for (int j = i + 1; j < nums.length; j++) {             //第二次循環(huán)確定第二個家數(shù)，不允許使用重復(fù)的同樣的數(shù)字，從第一個加數(shù)之后開始循環(huán)
                if (nums[j] == target - nums[i]) {                  
                    return new int[] { i, j };                      //題目假定一個輸入對應(yīng)一個結(jié)果，找到則直接輸出結(jié)果
                }
            }
        }

        throw new IllegalArgumentException("No two sum number");    //非法參數(shù)異常，對于輸入沒有指定的解
    ｝
｝

復(fù)雜度分析：

• 時間復(fù)雜度：O(n²)
• 空間復(fù)雜度：O(1)

2.哈希表

將一次遍歷轉(zhuǎn)換為哈希表（HashMap）

public class Solution2 {
    public int[] twoSum(int[] nums, int target){
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i<nums.length;i++){                             //定義哈希表，以元素的值為key，元素的位置為value
            map.put(nums[i], i);
        }
        for(int i =0 ;i<nums.length;i++){                              //遍歷數(shù)組，對于每一個值在哈希表中尋找對應(yīng)的值使之相加為target目標(biāo)值
            int complement = target - nums[i];
            if(map.containsKey(complement) && map.get(complement)!=i){ //判斷條件為該對應(yīng)值存在且和遍歷值不為同一個
                return new int[]{i,map.get(complement)};
            }
        }

        throw new IllegalArgumentException("No two sum");              //非法參數(shù)異常，對于輸入沒有指定的解
    }

復(fù)雜度分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

 public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        //一次循環(huán)，在往哈希表中添加元素的同時也檢驗是否存在符合的解
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(nums[i]) != i) {
                return new int[] { nums[i], complement };
            }
        }

        throw new IllegalArgumentException("No two sum");            //非法參數(shù)異常，對于輸入沒有指定的解
    }

復(fù)雜度分析：

• 時間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)

當(dāng)數(shù)組的長度超過一定的范圍時，使用HashMap的思想會更好