英雄游戏

43. 三数之和

难度感：medium

题目

给定整数数组，返回所有不重复的三元组 [a,b,c]，使得 a + b + c = 0。

题解

• 先排序，固定第一个数。
• 剩下两个数用左右指针向中间夹逼。
• 遇到重复值要跳过，避免重复三元组。

复杂度：O(n^2) 时间，排序外 O(1) 额外空间。

C# 答案

using System;
using System.Collections.Generic;

public class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        Array.Sort(nums);
        List<IList<int>> ans = new List<IList<int>>();

        for (int i = 0; i < nums.Length; i++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.Length - 1;
            while (l < r)
            {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0)
                {
                    ans.Add(new List<int> { nums[i], nums[l], nums[r] });
                    l++; r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                }
                else if (sum < 0) l++;
                else r--;
            }
        }

        return ans;
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;

        for (int i = 0; i < (int)nums.size(); ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    ans.push_back({nums[i], nums[l], nums[r]});
                    l++; r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return ans;
    }
};

---

44. 用栈实现二叉树前序遍历

难度感：medium

题目

给定二叉树根节点，使用栈实现非递归前序遍历，返回访问序列。前序顺序是：根、左、右。

题解

• 栈是后进先出。
• 为了让左子节点先访问，入栈时要先压右子节点，再压左子节点。
• 每次弹出一个节点就加入答案。

复杂度：O(n) 时间，O(h) 到 O(n) 空间。

C# 答案

using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left, right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public IList<int> PreorderTraversal(TreeNode root)
    {
        List<int> ans = new List<int>();
        if (root == null) return ans;

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);

        while (stack.Count > 0)
        {
            TreeNode node = stack.Pop();
            ans.Add(node.val);

            if (node.right != null) stack.Push(node.right);
            if (node.left != null) stack.Push(node.left);
        }

        return ans;
    }
}

C++ 答案

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (!root) return ans;

        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            ans.push_back(node->val);

            if (node->right) st.push(node->right);
            if (node->left) st.push(node->left);
        }
        return ans;
    }
};