【JAVA刷题初阶】刷爆力扣第三弹——数组

---

🌕 前言：关于JAVA刷题

🤙关于JAVA的学习出了看视频以外，那就是刷题了，朋友们，你们有没有过这样的感觉，在网上看了视频过后感觉自己什么都听懂了，但就是写题和做项目时无从下手，或者就是因为某个细节一直错一直改，那背后的原因是什么呢？四个字——题刷少了，这里新一建议去Leetcode看看，那里的题库资源很丰富，并且在全球都有广泛涉猎。不仅如此，这里还有 课程 + 刷题 + 面经 + 求职 + 讨论区分享解题思路，用过的人都说好😜

👉除此之外，我的建议是初学者从简单题开始练习，因为简单题是一切题的基础，一切的困难题都是从简单题衍生而来的，每天刷那么2~3题，后期再慢慢刷中等题，困难题，经过一段时间后会有很不错的提升

此外，在我们有一定的提升之后，我们便可以去刷剑指offer了，在这里预祝各位大学生以及初学者都拿到自己满意的offer！💖

---

第一题：合并两个有序数组

👇👇👇
做题链接戳这里：88.合并两个有序数组

🍂 题目描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

🍂示例

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例2

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例3

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

🍂提示

● nums1.length == m + n
● nums2.length == n
● 0 <= m, n <= 200
● 1 <= m + n <= 200
● -109 <= nums1[i], nums2[j] <= 109

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

🍃题解

常规思路：

第一种办法很容易想到，那就是不管三七二十一直接全部将nums2中元素全部放入nums1中，然后再暴力排序。

public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m++] = nums2[i];
        }
        Arrays.sort(nums1);
    }
1
2
3
4
5
6

从后往前倒放：

好了，我们的重头戏来了，这样的代码虽然方便但是时间复杂度太高了，我们能否将它优化一下？我们用数组的思想，从后往前排，因为无论怎么想，最大的元素肯定是要排在最后的，那么我们不妨先从最大元素开始排，那样不用移动元素，最后如果没排完直接将剩余元素放进去即可

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0){
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        while (n >= 0){
            nums1[p--] = nums2[n--];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11

第二题：杨辉三角

👇👇👇
做题链接戳这里，118.杨辉三角

🍂 题目描述

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

🍂示例

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例2

输入: numRows = 1
输出: [[1]]

🍂提示

● 1 <= numRows <= 30

🍃题解

这里我们创建一个二维数组，也就是List>，之后将每行元素放进去即可，需要注意的是第一行和最后一行的值

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> lists = new ArrayList<>();

        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        lists.add(list1);

        for (int i = 1; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            for (int j = 1; j < i; j++) {
                List<Integer> prevRows = lists.get(i - 1);
                list.add(prevRows.get(j) + prevRows.get(j - 1));
            }
            list.add(1);
            lists.add(list);
        }
        return lists;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第三题：两数之和

👇👇👇
做题链接戳这里：1.两数之和

🍂 题目描述

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

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

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

🍂示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例2

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例3

输入：nums = [3,3], target = 6
输出：[0,1]

🍂提示

● 2 <= nums.length <= 104
● -109 <= nums[i] <= 109
● -109 <= target <= 109
● 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

🍃题解

常规思路

首先，我们最容易想到的就是嵌套遍历数组，找到与当前值对应的target - nums[ i ]值，即可返回，但缺点就是时间复杂度太高

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == target - nums[j]){
                    answer[0] = i;
                    answer[1] = j;
                    return answer;
                }
            }
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

ArrayList解法

这里还有一种解法就是利用我们的ArrayList，把每个target - nums[ i ]的值都存放在我们的数组中，然后每次用indexOf方法查找与之对应的值即可

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (list.contains(nums[i])){
                answer[0] = i;
                answer[1] = list.indexOf(nums[i]);
            }
            list.add(target - nums[i]);
        }
        return answer;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

虽然看着只循环遍历了一次，但我们调用的方法也耗费了时间，故时间复杂度跟前一个差不多

HashMap解法

我们知道用空间换取时间的理论，这种理论在HashMap上完美的体现了出来

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
        for(int i = 0; i < nums.length; i++){
            if(hash.containsKey(nums[i])){
                indexs[0] = i;
                indexs[1] = hash.get(nums[i]);
                return indexs;
            }
            hash.put(target-nums[i],i);
        }
        return indexs;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

嗯，HashMap 永远滴神