刷算法(1)-两数之和

1. 两数之和

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

第一种做法：暴力破解

package com.yangq.test;

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] results = new int[] {0, 0};
        for (int i =0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    results[0] = i;
                    results[1] = j; 
                }
            }

        }
        return results;    
    }
}

时间复杂度：O(n^2)，空间复杂度O(1)。

第二种做法:一遍哈希

class Solution {
    public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> data = new HashMap<Integer, Integer>();
        
        for (int i = 0; i< nums.length; i++) {
            int diff = target - nums[i];
            if (data.containsKey(diff)) {
                return new int[] {i, data.get(diff)};
            }
            data.put(nums[i], i);
        }
        throw new IllegalArgumentException("can't found");  
    }
}

• 时间复杂度：O(n)，我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)的时间。

• 空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n个元素。