“This is the 20th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Topic describes

This is 1748 on LeetCode. The sum of the only elements is easy.

Tag: “simulation”, “hash table”, “double pointer”, “sort”

Give you an integer array nums. The only elements in the array are those that occur “exactly once.”

Return the sum of the unique elements in NUMS.

Example 1:

Input: nums = [1,2,3,2] output: 4 explanation: the unique elements are [1,3] and are 4.Copy the code

Example 2:

Input: nums = [1,1,1,1,1] output: 0 explanation: there are no unique elements and the sum is 0.Copy the code

Example 3:

Input: nums = [1,2,3,4,5] output: 15 explanation: the unique elements are [1,2,3,4,5], and are 15.Copy the code

Tip:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

Sort + double pointer

[I,j] [I,j)[I,j)[I,j)[I,j). If the length of the continuous segment is 111, add the value to the answer.

Code:

class Solution {
    public int sumOfUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, ans = 0;
        for (int i = 0; i < n; ) {
            int j = i;
            while (j < n && nums[j] == nums[i]) j++;
            if (j - i == 1) ans += nums[i];
            i = j;
        }
        returnans; }}Copy the code
  • Time complexity: the sorting complexity is O(nlog⁡n)O(n\log{n})O(nlogn); The complexity of the statistical answer is O(n)O(n)O(n). The overall complexity is O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(log⁡n)O(\log{n})O(logn)

Hash table

Nums [I]nums[I]nums[I]nums[I] range of [1,100][1, 100][1,100], can be used as a hash table.

Code:

class Solution {
    int[] cnt = new int[110];
    public int sumOfUnique(int[] nums) {
        for (int i : nums) cnt[i]++;
        int ans = 0;
        for (int i = 1; i <= 100; i++) {
            if (cnt[i] == 1) ans += i;
        }
        returnans; }}Copy the code
  • Time complexity: Set CCC to the value of NUMs [I]nums[I]nums[I]. In this case, the value is fixed to 110110110. The overall complexity is O(n+C)O(n +C)O(n +C)
  • Space complexity: O(C)O(C)O(C)

The last

This is the No.1748 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.