算法通关村番外篇-面试150题二

?
大家好我是苏麟 , 今天开始LeetCode面试经典150题 .

?

1. 两数之和

描述 :

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

题目 :

LeetCode 两数之和

分析 :

暴力解法 , 哈希解法 . 没什么说的 .

代码 :

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[]{};
    }
}

167. 两数之和 II - 输入有序数组

描述 :

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

题目 :

LeetCode 两数之和 II - 输入有序数组

分析 :

双指针 , 二分查找法 .

代码 :

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }
}

15. 三数之和

描述 :

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

题目 :

LeetCode 三数之和

分析 :

这道题不容易想 , 先理解两数之和 .

代码 :

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        int n = nums.length - 1;
        Arrays.sort(nums);
        for(int i = 0;i <= n ; i++){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            int k = n;
            int targer = -nums[i];
            for(int j = i + 1 ; j <= n ;j++){
                if(j > i + 1 && nums[j] == nums[j - 1]){
                    continue;
                }
                while(j < k && nums[j] + nums[k] > targer){
                    k--;
                }
                if( j == k){
                    break;
                }
                if(nums[j] + nums[k] == targer){
                    List<Integer> l = new ArrayList<>();
                    l.add(nums[i]);
                    l.add(nums[j]);
                    l.add(nums[k]);
                    list.add(l);
                }
            }
        }
        return list;
    }
}

这期就到这里 , 下期见!