给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

链接:https://leetcode-cn.com/problems/two-sum/

示例:

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

暴力破解:

两层for循环,针对每一个数 n,遍历里面是否有另外一个数为target-n
时间复杂度为O(n^2),空间复杂度为O(1)

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

空间换时间

借助hashmapkey为元素的值,value为元素的下标,将数字不断放进hashmap,放之前判断里面是否存在target-num

    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        if (nums == null || nums.length == 0) {
            return result;
        }
        Map<Integer, Integer> numSet = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numSet.containsKey(target - nums[i])) {
                result[0] = numSet.get(target - nums[i]);
                result[1] = i;
                return result;
            } else {
                numSet.put(nums[i], i);
            }
        }
        return result;
    }

复杂度分析:

  • 时间复杂度:O(N),遍历了所有的数。
  • 空间复杂度:O(N),hashMap的大小最大为n。

【作者简介】
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。这个世界希望一切都很快,更快,但是我希望自己能走好每一步,写好每一篇文章,期待和你们一起交流。

此文章仅代表自己(本菜鸟)学习积累记录,或者学习笔记,如有侵权,请联系作者核实删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有错误之处,还望指出,感激不尽~

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

纵然缓慢,驰而不息。