数据结构-1-两数之和

数据结构-1-两数之和

方法一、直接两层for遍历

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] ret=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){
                    ret[0]=i;
                    ret[1]=j;
                    return ret;
                }
            }
        }
        return null;
    }
}

方法二、哈希表

哈希表是根据key和散列函数直接得到存储位置的一种数据结构。

这个解法就是逐个把数放进去,一边放一边检测target-这个数在哈希表中是否存在。由此达到O(N)复杂度。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> hashtable=new HashMap<Integer,Integer>();
        for(int i = 0;i < nums.length;i++){
            if(hashtable.containsKey(target-nums[i])){
                return new int[]{hashtable.get(target-nums[i]),i};
            }
            hashtable.put(nums[i],i);
        }
        return null;
    }
}

注意HashMap的创建:Map<Integer,Integer> hashtable=new HashMap<Integer,Integer>();

使用:get,put,containsKey

上一篇:Address already in use: connect


下一篇:【LeetCode】394. 字符串解码