leetcode 977

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.

Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach?

我的解法

public class SquaresSortedArray {
    public int[] sortedSquares(int[] nums) {
        int [] results = new int[nums.length];
        int index = nums.length - 1;
        for (int i = 0, j = nums.length - 1; i <= j; ) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                results[index] = nums[i] * nums[i];
                index--;
                i++;
            } else {
                results[index] = nums[j] * nums[j];
                index--;
                j--;
            }
        }
        return results;
    }
}

977. 有序数组的平方

给你一个按非递减顺序排列的整数数组 nums，返回一个由每个数字的平方组成的新数组，要求也按非递减顺序排列。

---

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后数组变为 [16,1,0,9,100]，排序后变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

---

约束条件：

• 1 <= nums.length <= 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 按非递减顺序排列

---

进阶： 对每个元素平方后排序是很简单的做法，你能找到一种 O(n) 时间复杂度的不同解法吗？

---

💡 解题思路

方法一：暴力法（简单但不够优）
直接平方后排序，时间复杂度 O(n log n)

方法二：双指针法（O(n) 最优解）✅

由于数组已排序，最大值一定在两端（负数越小平方越大，正数越大平方越大）。

用双指针从两端向中间靠拢，每次取平方较大的那个放入结果数组的末尾。

---

☕️ Java 实现

class Solution {
    /**
     * LeetCode 977: 有序数组的平方 - 双指针法
     * 时间 O(n)，空间 O(n)（返回数组）
     */
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        int left = 0;          // 左指针
        int right = n - 1;     // 右指针
        int pos = n - 1;       // 从结果数组末尾开始填充
        
        while (left <= right) {
            int leftSq = nums[left] * nums[left];
            int rightSq = nums[right] * nums[right];
            
            if (leftSq > rightSq) {
                result[pos] = leftSq;
                left++;
            } else {
                result[pos] = rightSq;
                right--;
            }
            pos--;
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 示例 1
        int[] nums1 = {-4, -1, 0, 3, 10};
        int[] res1 = sol.sortedSquares(nums1);
        System.out.print("输出: [");
        for (int i = 0; i < res1.length; i++) {
            System.out.print(res1[i] + (i < res1.length - 1 ? "," : ""));
        }
        System.out.println("]");
        // 输出: [0,1,9,16,100]

        // 示例 2
        int[] nums2 = {-7, -3, 2, 3, 11};
        int[] res2 = sol.sortedSquares(nums2);
        System.out.print("输出: [");
        for (int i = 0; i < res2.length; i++) {
            System.out.print(res2[i] + (i < res2.length - 1 ? "," : ""));
        }
        System.out.println("]");
        // 输出: [4,9,9,49,121]
    }
}

---

🧮 执行过程演示

以 nums = [-4,-1,0,3,10] 为例：

初始: left=0, right=4, pos=4

第1轮: leftSq=16, rightSq=100 → 100更大
  result[4]=100, right=3, pos=3
  result = [_,_,_,_,100]

第2轮: leftSq=16, rightSq=9 → 16更大
  result[3]=16, left=1, pos=2
  result = [_,_,_,16,100]

第3轮: leftSq=1, rightSq=9 → 9更大
  result[2]=9, right=2, pos=1
  result = [_,_,9,16,100]

第4轮: leftSq=1, rightSq=0 → 1更大
  result[1]=1, left=2, pos=0
  result = [_,1,9,16,100]

第5轮: leftSq=0, rightSq=0 → 相等
  result[0]=0, right=1, pos=-1
  result = [0,1,9,16,100]

left > right，结束 ✅

---

💡 核心要点

为什么从后往前填
• 说明: 两端平方值最大，先确定最大值

为什么双指针
• 说明: 有序数组，最大值一定在两端

时间复杂度
• 说明: O(n) — 只遍历一次

空间复杂度
• 说明: O(n) — 返回结果数组

这道题是双指针的经典应用，和 LeetCode 26、27 一样都是数组双指针技巧

leetcode 344

344. Reverse String
     Solved
     Easy
     Topics
     premium lock icon
     Companies
     Hint
     Write a function that reverses a string. The input string is given as an array of characters s.

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2:

Input: s = [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

Constraints:

1 <= s.length <= 105
s[i] is a printable ascii character.

我的写法

public void reverseString(char[] s) {
    int n = s.length;
    char[] s2 = new char[n];
    for(int i=0;i<n; i++){
        s2[n-i-1] = s[i];
    }
    for (int i = 0; i <n ; i++) {
        s[i] = s2[i];
    }
}

📌 题目翻译

344. 反转字符串

简单

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

你必须原地修改输入数组，使用 O(1) 的额外空间。

---

示例 1：

输入：s = [“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]

示例 2：

输入：s = [“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]

---

约束条件：

• 1 <= s.length <= 10⁵
• s[i] 是可打印的 ASCII 字符

---

💡 解题思路

双指针法：一个指针从头，一个从尾，逐步向中间靠拢，交换两个指针指向的字符。

• 时间复杂度：O(n)
• 空间复杂度：O(1) — 原地修改

---

☕️ Java 实现

class Solution {
    /**
     * LeetCode 344: 反转字符串
     * 时间 O(n)，空间 O(1)
     */
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while (left < right) {
            // 交换左右指针的字符
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            
            left++;
            right--;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 示例 1
        char[] s1 = {'h','e','l','l','o'};
        sol.reverseString(s1);
        System.out.println(java.util.Arrays.toString(s1));
        // 输出: [o, l, l, e, h]

        // 示例 2
        char[] s2 = {'H','a','n','n','a','h'};
        sol.reverseString(s2);
        System.out.println(java.util.Arrays.toString(s2));
        // 输出: [h, a, n, n, a, H]
    }
}

---

🧮 执行过程演示

以 s = ['h','e','l','l','o'] 为例：

初始:  h  e  l  l  o
       ↑           ↑
     left        right

第1轮: 交换 s[0]='h' 和 s[4]='o'
       o  e  l  l  h
          ↑     ↑
        left  right

第2轮: 交换 s[1]='e' 和 s[3]='l'
       o  l  l  e  h
             ↑
          left=right → 结束

结果: [o, l, l, e, h] ✅

---

💡 核心要点

双指针
• 说明: 左右夹逼，逐步交换

终止条件
• 说明: left >= right 时停止

为什么原地
• 说明: 只用了 temp 一个变量，O(1) 空间

时间复杂度
• 说明: O(n/2) = O(n)

这是最简单的双指针入门题，也是面试高频热身题 🔥

leetcode 15

15. 3Sum
    Medium
    Topics
    premium lock icon
    Companies
    Hint
    Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

没有写出来！！！

15. 三数之和

中等

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

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

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

---

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

解释：

• nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
• nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
• nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0

不同的三元组是 [-1,0,1] 和 [-1,-1,2]。注意输出的顺序和三元组内部的顺序不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0。

---

💡 解题思路：排序 + 双指针

1. 排序 — 方便去重和使用双指针
2. 固定第一个数 nums[i]，然后用双指针在剩余部分找两数之和等于 -nums[i]
3. 去重 — 跳过重复元素，避免结果重复

时间复杂度：O(n²) — 外层循环 O(n)，内层双指针 O(n)
空间复杂度：O(1) — 排序原地进行（忽略输出空间）

---

☕️ Java 实现

class Solution {
    /**
     * LeetCode 15: 三数之和
     * 排序 + 双指针，时间 O(n²)，空间 O(1)
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 先排序

        for (int i = 0; i < nums.length - 2; i++) {
            // 剪枝1：如果最小的数已经 > 0，后面不可能有三数之和为 0
            if (nums[i] > 0) break;

            // 去重：跳过重复的 nums[i]
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i]; // 需要找的两数之和

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == target) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重：跳过重复的 nums[left]
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 去重：跳过重复的 nums[right]
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;
                } else if (sum < target) {
                    left++; // 和太小，左指针右移
                } else {
                    right--; // 和太大，右指针左移
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();

        // 示例 1
        int[] nums1 = {-1, 0, 1, 2, -1, -4};
        System.out.println(sol.threeSum(nums1));
        // 输出: [[-1, -1, 2], [-1, 0, 1]]

        // 示例 2
        int[] nums2 = {0, 1, 1};
        System.out.println(sol.threeSum(nums2));
        // 输出: []

        // 示例 3
        int[] nums3 = {0, 0, 0};
        System.out.println(sol.threeSum(nums3));
        // 输出: [[0, 0, 0]]
    }
}

---

🧮 执行过程演示

以 nums = [-1,0,1,2,-1,-4] 为例：

排序后: [-4, -1, -1, 0, 1, 2]

i=0, nums[0]=-4, target=4
  left=1(-1), right=5(2) → sum=1 < 4 → left++
  left=2(-1), right=5(2) → sum=1 < 4 → left++
  left=3(0),  right=5(2) → sum=2 < 4 → left++
  left=4(1),  right=5(2) → sum=3 < 4 → left++
  left >= right → 无结果

i=1, nums[1]=-1, target=1
  left=2(-1), right=5(2) → sum=1 == 1 → ✅ [-1,-1,2]
    去重后 left=3, right=4
  left=3(0),  right=4(1) → sum=1 == 1 → ✅ [-1,0,1]
    left=4, right=3 → 结束

i=2, nums[2]=-1 == nums[1] → 跳过（去重）

i=3, nums[3]=0, target=0
  left=4(1), right=5(2) → sum=3 > 0 → right--
  left >= right → 无结果

最终结果: [[-1,-1,2], [-1,0,1]] ✅

---

💡 核心要点

排序
• 说明: 是双指针和去重的前提

固定一个数
• 说明: 把三数之和转化为两数之和

去重三处
• 说明: ① 固定数去重 ② left 去重 ③ right 去重

剪枝
• 说明: nums[i] > 0 时直接 break

时间复杂度
• 说明: O(n²) — 排序 O(n log n) + 双指针 O(n²)

这是 LeetCode 最经典的双指针题目之一，面试超高频