给定一个整数数组和一个整数,返回两个数组的索引-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

给定一个整数数组和一个整数,返回两个数组的索引

Runt 2020-04-14 18:30:02 1327

题目:给定一个整数数组和一个整数,返回两个数组的索引,这两个索引指向的数字的加和等于指定的整数。需要最优的算法,分析算法的空间和时间复杂度

算法 索引
分享到
取消 提交回答
全部回答(2)
  • 景凌凯
    2020-04-15 22:52:27

    public static int[] twoSum(int[] numbers, int target) { int i = 0, j = numbers.length - 1;

        while (i != j) {
            if (numbers[i] + numbers[j] == target) {
                return new int[]{i + 1, j + 1};
            }
    
            if (numbers[i] + numbers[j] < target) {
                i++;
                continue;
            }
    
            if (numbers[i] + numbers[j] > target) {
                j--;
                continue;
            }
        }
    
        return new int[]{i, j};
    }
    
    0 0
  • Runt
    2020-04-14 18:30:34

    参考答案:

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

    分析:空间复杂度和时间复杂度均为 O(n)

    0 0
添加回答
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题