1748-唯一元素的和

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个整数数组 nums 。数组中唯一元素是那些只出现 恰好一次 的元素。

请你返回 nums 中唯一元素的 和 。

示例 1：

**输入：** nums = [1,2,3,2]
**输出：** 4
**解释：** 唯一元素为 [1,3] ，和为 4 。

示例 2：

**输入：** nums = [1,1,1,1,1]
**输出：** 0
**解释：** 没有唯一元素，和为 0 。

示例 3 ：

**输入：** nums = [1,2,3,4,5]
**输出：** 15
**解释：** 唯一元素为 [1,2,3,4,5] ，和为 15 。

提示：

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

方法一：记录每个元素的出现次数

根据题意，我们可以用一个哈希表记录每个元素值的出现次数，然后遍历哈希表，累加恰好出现一次的元素值，即为答案。

[sol1-Python3]
1
2
3
class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        return sum(num for num, cnt in Counter(nums).items() if cnt == 1)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int sumOfUnique(vector<int> &nums) {
        unordered_map<int, int> cnt;
        for (int num : nums) {
            ++cnt[num];
        }
        int ans = 0;
        for (auto &[num, c] : cnt) {
            if (c == 1) {
                ans += num;
            }
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int sumOfUnique(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int num : nums) {
            cnt.put(num, cnt.getOrDefault(num, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int num = entry.getKey(), c = entry.getValue();
            if (c == 1) {
                ans += num;
            }
        }
        return ans;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int SumOfUnique(int[] nums) {
        Dictionary<int, int> cnt = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!cnt.ContainsKey(num)) {
                cnt.Add(num, 0);
            }
            ++cnt[num];
        }
        int ans = 0;
        foreach (KeyValuePair<int, int> pair in cnt) {
            int num = pair.Key, c = pair.Value;
            if (c == 1) {
                ans += num;
            }
        }
        return ans;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
func sumOfUnique(nums []int) (ans int) {
    cnt := map[int]int{}
    for _, num := range nums {
        cnt[num]++
    }
    for num, c := range cnt {
        if c == 1 {
            ans += num
        }
    }
    return
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef struct {
    int key;                  
    int val;
    UT_hash_handle hh;         
} HashEntry;

int sumOfUnique(int* nums, int numsSize){
    HashEntry * cnt = NULL; 
    for (int i = 0; i < numsSize; ++i) {
        HashEntry * pEntry = NULL;
        HASH_FIND(hh, cnt, &nums[i], sizeof(int), pEntry);
        if (NULL == pEntry) {
            pEntry = (HashEntry *)malloc(sizeof(HashEntry));
            pEntry->key = nums[i];
            pEntry->val = 1;
            HASH_ADD(hh, cnt, key, sizeof(int), pEntry);
        } else {
            ++pEntry->val;
        }
    }
    int ans = 0;
    HashEntry *curr, *next;
    HASH_ITER(hh, cnt, curr, next) {
        if (curr->val == 1) {
            ans += curr->key;
        } 
    }
    HASH_ITER(hh, cnt, curr, next)
    {
        HASH_DEL(cnt, curr);  
        free(curr);      
    }
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
var sumOfUnique = function(nums) {
    const cnt = new Map();
    for (const num of nums) {
        cnt.set(num, (cnt.get(num) || 0) + 1);
    }
    let ans = 0;
    for (const [num, c] of cnt.entries()) {
        if (c === 1) {
            ans += num;
        }
    }
    return ans;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(n)。哈希表需要 O(n) 的空间。

方法二：记录每个元素的状态 + 一次遍历

方法一需要遍历数组和哈希表各一次，能否做到仅执行一次遍历呢？

我们可以赋给每个元素三个状态：

  • 0：该元素尚未被访问；
  • 1：该元素被访问过一次；
  • 2：该元素被访问超过一次。

我们可以在首次访问一个元素时，将该元素加入答案，然后将该元素状态标记为 1。在访问到一个标记为 1 的元素时，由于这意味着该元素出现不止一次，因此将其从答案中减去，并将该元素状态标记为 2。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def sumOfUnique(self, nums: List[int]) -> int:
        ans = 0
        state = {}
        for num in nums:
            if num not in state:
                ans += num
                state[num] = 1
            elif state[num] == 1:
                ans -= num
                state[num] = 2
        return ans
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int sumOfUnique(vector<int> &nums) {
        int ans = 0;
        unordered_map<int, int> state;
        for (int num : nums) {
            if (state[num] == 0) {
                ans += num;
                state[num] = 1;
            } else if (state[num] == 1) {
                ans -= num;
                state[num] = 2;
            }
        }
        return ans;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int sumOfUnique(int[] nums) {
        int ans = 0;
        Map<Integer, Integer> state = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!state.containsKey(num)) {
                ans += num;
                state.put(num, 1);
            } else if (state.get(num) == 1) {
                ans -= num;
                state.put(num, 2);
            }
        }
        return ans;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int SumOfUnique(int[] nums) {
        int ans = 0;
        Dictionary<int, int> state = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (!state.ContainsKey(num)) {
                ans += num;
                state.Add(num, 1);
            } else if (state[num] == 1) {
                ans -= num;
                state[num] = 2;
            }
        }
        return ans;
    }
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
func sumOfUnique(nums []int) (ans int) {
    state := map[int]int{}
    for _, num := range nums {
        if state[num] == 0 {
            ans += num
            state[num] = 1
        } else if state[num] == 1 {
            ans -= num
            state[num] = 2
        }
    }
    return
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
typedef struct {
    int key;                  
    int val;
    UT_hash_handle hh;         
} HashEntry;

int sumOfUnique(int* nums, int numsSize){
    HashEntry * cnt = NULL; 
    int ans = 0;
    for (int i = 0; i < numsSize; ++i) {
        HashEntry * pEntry = NULL;
        HASH_FIND(hh, cnt, &nums[i], sizeof(int), pEntry);
        if (NULL == pEntry) {
            pEntry = (HashEntry *)malloc(sizeof(HashEntry));
            pEntry->key = nums[i];
            pEntry->val = 1;
            ans += nums[i];
            HASH_ADD(hh, cnt, key, sizeof(int), pEntry);
        } else if (pEntry->val == 1){
            ans -= nums[i];
            pEntry->val = 2;
        }
    }
    HashEntry *curr = NULL, *next = NULL;
    HASH_ITER(hh, cnt, curr, next)
    {
        HASH_DEL(cnt, curr);  
        free(curr);      
    }
    return ans;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var sumOfUnique = function(nums) {
    let ans = 0;
    const state = new Map();
    for (const num of nums) {
        if (!state.has(num)) {
            ans += num;
            state.set(num, 1);
        } else if (state.get(num) === 1) {
            ans -= num;
            state.set(num, 2);
        }
    }
    return ans;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(n)。哈希表需要 O(n) 的空间。

 Comments
On this page
1748-唯一元素的和