334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

link

Example 1:

Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.

Example 2:

Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.

Example 3:

Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

解题思路

1. 双向遍历

```c++ class Solution { public: bool increasingTriplet(vector& nums) { int n=nums.size(); vector leftMin(n,nums[0]); vector rightMax(n,nums[n-1]); for(int i=1;i<n;i++){ if(nums[i]<leftMin[i-1]){ leftMin[i]=nums[i]; }else{ leftMin[i]=leftMin[i-1]; } if(nums[n-i-1]>rightMax[n-i]){ rightMax[n-i-1]=nums[n-i-1]; }else{ rightMax[n-i-1]=rightMax[n-i]; } } for(int i=1;i<n-1;i++){ if(leftMin[i-1]<nums[i]&&rightMax[i+1]>nums[i]) return true; } return false; } };

2.贪心

```C++
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        int first = nums[0], second = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            int num = nums[i];
            if (num > second) {
                return true;
            } else if (num > first) {
                second = num;
            } else {
                first = num;
            }
        }
        return false;
    }
}

238. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

link

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

解题思路

1. 左右乘积表

```c++ class Solution { public: vector productExceptSelf(vector& nums) { int n=nums.size(); vector L(n,1),R(n,1),ans(n); for(int i=1;i<n;i++){ L[i]=L[i-1]nums[i-1]; R[n-i-1]=R[n-i]nums[n-i]; } for(int i=0;i<n;i++){ ans[i]=L[i]*R[i]; } return ans; } };

2. 空间复杂度为O(1)

```c++
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int> answer(length);

        // answer[i] 表示索引 i 左侧所有元素的乘积
        // 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1
        answer[0] = 1;
        for (int i = 1; i < length; i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // R 为右侧所有元素的乘积
        // 刚开始右边没有元素，所以 R = 1
        int R = 1;
        for (int i = length - 1; i >= 0; i--) {
            // 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 R
            answer[i] = answer[i] * R;
            // R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上
            R *= nums[i];
        }
        return answer;
    }
};

560. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

link

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

解题思路

1. 前缀和

```C++ class Solution { public: int subarraySum(vector& nums, int k) { int pre=0,count = 0; unordered_map<int,int> mp; mp[0]=1; for(auto num:nums){ pre+=num; if(mp.find(pre-k)!=mp.end()){ count+=mp[pre-k]; } mp[pre]++; } return count; } };