1.两数之和

1. 暴力解法

/** * 描述 暴力解法 O(n^2) */
class Solution {
    
    public int[] twoSum(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[]{
    };
    }

    public static void main(String[] args) {
    
        Solution solution = new Solution();
        int[] ints = solution.twoSum(new int[]{
    2, 7, 11, 15}, 9);
        System.out.println(ints[0] + " " + ints[1]);
    }
}

2. 哈希表

/** * 项目名： leetcode * 包名: com.kcl.L1 * 文件名 Solution * 创建者 * 创建时间: 2022/7/10 10:49 AM * 描述 hash O(n) */
class Solution2 {
    
    public int[] twoSum(int[] nums, int target) {
    
        Map<Integer,Integer> map = new HashMap<>();
        int len = nums.length;
        for(int i = 0; i < len; i++){
    
            //往前找
            if(map.get(target-nums[i]) != null){
    
               return new int[]{
    i,map.get(target-nums[i])};
            }else{
    
                map.put(nums[i],i);
            }
        }
        return new int[]{
    };
    }

    public static void main(String[] args) {
    
        Solution2 solution = new Solution2();
        int[] ints = solution.twoSum(new int[]{
    2, 7, 11, 15}, 9);
        System.out.println(ints[0] + " " + ints[1]);
    }
}