Leetcode：计算时间复杂度为O（n）的元素

Question

给定一个整数数组arr，计算元素x，使得x 1也在arr中。如果arr中有重复项，请分别计数。

示例1：输入：arr=[1,2,3]输出：2说明：1和2被计数，因为2和3在arr中。

示例2：输入：arr=[1,1,2]输出：2解释：1计数两次，原因2在arr中。

示例3：输入：arr=[1,1,3,3,5,5,7,7]输出：0说明：没有计算数字，因为arr中没有2、4、6或8。

示例4：输入：arr=[1,1,2,2]输出：2解释：两个1被计数，因为2在arr中。

MyCode：（仅对示例2不起作用（目前））

int count = 0;
HashSet set = new HashSet();
for(int i=0;i<arr.length;i++) {
    if(set.contains(arr[i]-1) || set.contains(arr[i]+1)) {
        count++;
        set.add(arr[i]);
    }else {
        set.add(arr[i]);
    }
}
return count;

Answer 1

简单解决方案

class Solution:
    def countElements(self, arr: List[int]) -> int:
        c=0
        for i in arr:
         if(i+1 in arr):
                c+=1
        if(c>0):
            return c
        else:
            return 0```

Answer 2

Swift解决方案O（n）

class Solution {
    func countElements(_ arr: [Int]) -> Int {
        var arrSet = Set(arr)
        var result = 0

        for num in arr {
            if arrSet.contains(num+1) {
                result += 1
            }
        }
        return result
    }
}

Answer 3

你为什么要数arr[i]-1？。条件已设置。包含（arr[i]1）足够按照定义计算。

我想你是想一次就达到这个目标。这不起作用，因为您还必须计算重复发生的次数。

如果输入的顺序不同，示例2将起作用。例：[2,1,1]。您的解决方案更像是计算arr[i]1s，而不是计算这些数字本身。

这是我的代码2通：

class Solution {
    public int countElements(int[] arr) {
        Set<Integer> lookup = new HashSet<>();
        for(Integer i: arr){
            lookup.add(i);
        }
        
        int count =0;
        
        for(Integer i:arr){
            if(lookup.contains(i+1)){
                count++;
            }
        }
        return count;
    }
}

1. 将所有元素添加到集合。这具有O（n）的复杂性，并有助于O（1）查找。
2. 遍历数组，查看该元素是否存在于集合中。复杂度为O（n）*O（1）即O（n）

虽然我们迭代数组两次，但时间复杂度将为O（n）。