欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

两数之和(力扣)

程序员文章站 2024-02-21 14:36:28
...

两数之和(力扣)


import java.util.HashMap;

public class Test {
    public static void main(String[] args) {
        int[] arr = new int[]{2,7,11,15};
        int target = 9;
        System.out.println(test1(arr,target));
        System.out.println(test2(arr,target));
    }

    //双迭代数组,时间复杂度n*2
    public static String test1(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1;j < nums.length ;j++){
                if (nums[i] + nums[j] == target)
                    return "[" + i + "," + j +"]";
            }
        }
        return "No two sum solution";
    }

    //用hashmap存源数组,时间复杂度n,空间复杂度n,用空间换时间。
    public static String test2(int[] nums, int target) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i],i);
        }
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (hashMap.containsKey(temp) && hashMap.get(temp) != i){//确保数字不被用两次
                return "[" + i + "," + hashMap.get(temp) +"]";
            }
        }
        return "No two sum solution";
    }
}

 

相关标签: 每日一题