LeetCode 454 4Sum II

Posted on | In | 阅读

经典4Sum题，但是需要在4个数组中分别找到一个数来相加

暴力的方法需要O(N^4)的复杂度，普通的4Sum可以优化到O(N^3)，但是这题由于是在不同的数组中找，可以进一步的优化，把前两个数组里所有数的和放进一个哈希表，然后在后两个数组中找相反数的组合。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int sz = nums.size();
        if(sz < 3) {
            return false;
        }
        stack<int> st;
        int ak = INT_MIN;
        st.push(nums[sz-1]);
        for(int i = sz-1; i >= 0; --i) {
            if(nums[i] < ak) {
                return true;
            }
            while(!st.empty() && nums[i] > st.top()) {
                ak = max(ak, st.top());
                st.pop();
            }
            st.push(nums[i]);
        }
        return false;
    }
};