Leetcode题库1748. 唯一元素的和(c实现)

文章目录

• 思路
• 代码
• • 原始方法
  • 改进1后的方法

思路

数组元素范围1~100，直接建立hash数组，最后遍历数组，取出值为1的下标值相加

可改进：
1、改用状态转移，可将遍历次数降至一次(遍历次数降低，但指令级的时间复杂度未减少)
2、此处元素范围较小，可以直接作为下标，元素范围过大时，可建立较为稠密的映射表，降低空间复杂度

代码 原始方法

int sumOfUnique(int* nums, int numsSize){
    int Hash[101],Res=0;
    for(int i =0;i<101;i++){Hash[i]=0;}
    for(int i =0;i<numsSize;i++){Hash[nums[i]]++;}
    for(int i =0;i<101;i++){Res+=(Hash[i]==1)*i;}
    return Res;
}

改进1后的方法

int sumOfUnique(int* nums, int numsSize){
    int Hash[101],Res=0;
    for(int i =0;i<101;i++){Hash[i]=0;}
    for(int i =0;i<numsSize;i++){
        Hash[nums[i]]++;
        if(Hash[nums[i]]==1) Res+=nums[i];
        if(Hash[nums[i]]==2) Res-=nums[i];
    }
    return Res;
}