Fork me on GitHub

LeetCode-1：两数之和

发表于

本题为LeetCode第1道题，为简单题


给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来看看博主的暴力解法： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @author RickYinPeng
 * @ClassName Two_Sum
 * @Description LeetCode中第1道题
 * @date 2018/10/7/10:24
 *
 * 题目名称：两数之和
 */
public class Two_Sum {
    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int[] ints = twoSum(nums, 9);
        System.out.println(Arrays.toString(ints));
    }

    public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for(int j = i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return null;
    }
}

大佬的解法:

1
2
3
4
5
6
7
8
9
10
11
public static int[] twoSum_2(int[] nums,int target){
    Map<Integer, Integer> nums_map = new HashMap<>();
    for(int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if(nums_map.containsKey(complement)) {
            return new int[] {i, nums_map.get(complement)};
        }
        nums_map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No");
}


其实这个思路我之前也是有的，用结果循环减去数组内的值，判断数组内是否有差值，有的话不就直接找到了吗，不过，还是博主的眼界太低，只想着那几种找法，比如二分法….，转念一想，二分法需要数组有序，于是便打消了这个思路，转念用了暴力解法，还是太笨了。