LT_0001_两数之和

一、题目描述

 二、代码实现

2.1 暴力枚举

时间复杂度O(N^2)

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

2.2 哈希表

时间复杂度O(N)

public static int[] towSum(int[] nums, int target) {
        Map<Integer,Integer> hashtable = new HashMap<>();
        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 new int[0];
    }

三、测试代码

public static void main(String[] args) {
        int[] nums = {2,7,11,15};
        int target = 9;
        int[] result = {};

        result = towSum(nums,target);
        System.out.print("{");
        for (int i = 0; i < result.length; i++) {
            if (i != result.length - 1) {
                System.out.print(result[i] + ",");
            } else {
                System.out.print(result[i]);
            }
        }
        System.out.print("}");
    }

四、思路

本道题主要的一个思路就是先固定一个数X，然后再寻找target-X。