题目

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].

解析

给出一列整数数组和一个数字target，如果计算出数组中的两个数之和等于target，那么返回数组两个数的索引。

解答

基础的解法应该是将数组遍历之后取和，如果和等于target那么结束循环。这种解法的效率为O(n^2)。

    public int[] twoSum(int[] nums, int target) {
        int i,j;
        // 双层循环取和
        for(i=0;i<nums.length;i++){
            j=i+1;
            for(;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    int result[]=new int[]{i,j};
                    return result;
                }
            }
        }
        return null;
    }

更高效的解法可以通过将结果放入HashMap中，通过HashMap的containsKey的方法来查找答案。
相比于O(n)效率的数组循环，containsKey方法如果在计算hash值能立马找到key那么效率为O(1)，如果找不到key需要继续查找链表的话，那么效率为O(n)，但是又因为HashMap的hash值是分散的，所以查找链表的长度相比于数组循环的长度是更少的，所以总的来说HashMap的效率是更好的。

    public static int[] twoSum3(int[] nums , int target){
        Map<Integer,Integer> map = new HashMap<>();
        for(int i =0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }

版权声明：本文为benjamin4git原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/benjamin4git/p/10112441.html