> For the complete documentation index, see [llms.txt](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://celia-qian.gitbook.io/leetcode-notebook-2020-2021/linear-list/array/exercises.md).

# Exercises VII

## Single Number III

Medium

[原题链接](https://leetcode.com/problems/single-number-iii/)

### 描述

Given an integer array `nums`, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in **any order**.

**Follow up:** Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

### 例子

> Input: nums = \[1,2,1,3,2,5] 
>
> Output: \[3,5] 
>
> Explanation: \[5, 3] is also a valid answer.

### 解法 XOR

[出处](https://leetcode.com/problems/single-number-iii/discuss/68900/Accepted-C%2B%2BJava-O\(n\)-time-O\(1\)-space-Easy-Solution-with-Detail-Explanations)

Once again, we need to use XOR to solve this problem. But this time, we need to do it in two passes:

* In the first pass, we XOR all elements in the array, and get the XOR of the two numbers we need to find. Note that since the two numbers are distinct, so there must be a set bit (that is, the bit with value '1') in the XOR result. Find\
  out an arbitrary set bit (for example, the rightmost set bit).
* In the second pass, we divide all numbers into two groups, one with the aforementioned bit set, another with the before mentioned bit unset. Two different numbers we need to find must fall into the two district groups. XOR numbers in each group, we can find a number in either group.

**Complexity:**

* Time: *O* (*n*)
* Space: *O* (1)

**A Corner Case:**

* When `diff == numeric_limits<int>::min()`, `-diff` is also `numeric_limits<int>::min()`. Therefore, the value of `diff` after executing `diff &= -diff` is still `numeric_limits<int>::min()`. The answer is still correct.

```cpp
class Solution
{
public:
    vector<int> singleNumber(vector<int>& nums) 
    {
        // Pass 1 : 
        // Get the XOR of the two numbers we need to find
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        // Get its last set bit
        diff &= -diff;

        // Pass 2 :
        vector<int> rets = {0, 0}; // this vector stores the two numbers we will return
        for (int num : nums)
        {
            if ((num & diff) == 0) // the bit is not set
            {
                rets[0] ^= num;
            }
            else // the bit is set
            {
                rets[1] ^= num;
            }
        }
        return rets;
    }
};

```

## Count Good Triplets

[原题链接](https://leetcode.com/problems/count-good-triplets/)

easy

```cpp
class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int res=0; int n=arr.size();
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                for(int k=j+1; k<n; k++){
                    if(abs(arr[i]-arr[j])<=a&&abs(arr[j] - arr[k])<=b; abs(arr[i] - arr[k])<=c) res++;
                }
            }
        }
        return res; 
    }
};
```

这题其实出的挺烂的，但是有人做了[优化](https://leetcode.com/problems/count-good-triplets/discuss/768459/O\(n2\)-solution)->time: O(n^2)。

## Count Number of Teams

Medium

[原题链接](https://leetcode.com/problems/count-number-of-teams/)

**Count left and right**

For each soldier, count how many soldiers on the left and right have `less` and `greater` ratings.

This soldier can form `less[left] * greater[right] + greater[left] * less[right]` teams.

[解释](https://leetcode.com/problems/count-number-of-teams/discuss/555441/Java-100-O\(N2\)-Easy-To-Understand-With-Explanation)

```cpp
class Solution {
public:
    int numTeams(vector<int>& rating) {
        int res = 0;
        for(int i = 1; i < rating.size(); i++){
            int less[2] = {}, greater[2] = {};
            for(int j = 0; j < rating.size(); j++){
                if(rating[i] < rating[j])
                    ++less[j>i];
                if(rating[i] > rating[j])
                    ++greater[j>i];
            }
            res += less[0] * greater[1] + greater[0] * less[1];
        }
        return res;
    }
};
```

Time: O(n^2)

## Sum of All Odd Length Subarrays

[原题链接](https://leetcode.com/problems/sum-of-all-odd-length-subarrays/)

easy

Consider the subarray that contains `A[i]`,\
we can take 0,1,2..,i elements on the left,\
from A\[0] to A\[i],\
we have i + 1 choices.

we can take 0,1,2..,n-1-i elements on the right,\
from A\[i] to A\[n-1],\
we have n - i choices.

In total, there are `(i + 1) * (n - i)` subarrays, that contains `A[i]`.\
And there are `((i + 1) * (n - i) + 1) / 2` subarrays with odd length, that contains `A[i]`.\
`A[i]` will be counted `((i + 1) * (n - i) + 1) / 2` times.

**Example of array \[1,2,3,4,5]**

1 2 3 4 5 subarray length 1\
1 2 X X X subarray length 2\
X 2 3 X X subarray length 2\
X X 3 4 X subarray length 2\
X X X 4 5 subarray length 2\
1 2 3 X X subarray length 3\
X 2 3 4 X subarray length 3\
X X 3 4 5 subarray length 3\
1 2 3 4 X subarray length 4\
X 2 3 4 5 subarray length 4\
1 2 3 4 5 subarray length 5

5 8 9 8 5 total times each index was added.\
3 4 5 4 3 total times in odd length array with (x + 1) / 2\
2 4 4 4 2 total times in even length array with x / 2

```cpp
class Solution {
public:
  int sumOddLengthSubarrays(vector<int>& A) {
        int res = 0, n = A.size();
        for (int i = 0; i < n; ++i) {
            res += ((i + 1) * (n - i) + 1) / 2 * A[i];
        }
        return res;
    }
};
```

Time：O(N)&#x20;

Space: O(1)