包含重复为什么此代码堆栈溢出

Question

这是问题所在：

给定一个整数数组，查找该数组是否包含任何重复项。如果任何值在数组中至少出现两次，则函数应返回 true，如果每个元素都是不同的，则函数应返回 false。

这是我的代码，但堆栈溢出存在错误：

public static class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length < 1)
            return false;
        return recursion(nums, 0, nums.length - 1);
    }
    private static boolean recursion(int[] nums, int start, int end) {
        if ((end - start) == 0) {
            return true;
        }
        if ((end - start) == 1) {
            if (nums[start] == nums[end]) {
                return false;
            } else {
                return true;
            }
        }
        boolean first = recursion(nums, start, (end - start) / 2 - 1);
        boolean second = recursion(nums, (end - start) / 2, end);
        if (first == false || second == false) {
            return false;
        }
        return true;
    }
}

Answer 1

您可以

创建一个HashSet并检查密钥之前是否存在

public boolean containsDuplicate(final int[] nums)
{
  Set<Integer> set = new HashSet<Integer>();
  for (int i : nums) {
    if (set.contains(i)) return true;
    set.add(i);
  }
  return false;
}

Answer 2

这一行：布尔秒 = 递归（nums， （end - start）/2， end）;

尤其是这个：（结束 - 开始）/2

例：

开始 = 0结束 = 3

1. （3 - 0）/2 = 1

2. （3 - 1）/2 = 1

3. 。

开始将始终相同。

第一次递归会出现相同的行为，只是 start 将在 0 处被阻止。

Answer 3

我已经通过在我这边运行您的代码来重现您的错误 - 问题是recursion(nums, start, (end - start)/2 - 1)到了开始索引 = 2 并且结束索引-3的点 - 因此递归永远不会停止。

这是更正 - 我针对这样的数组对其进行了测试： int[] nums = new int[]{1,2,3,4,5,6,6};

private static boolean recursion(int[] nums, int start, int end) {
        if((end - start) == 0){ return false;}
        if((end - start) == 1){             
            //This is really where the recursion should end...unless if there were no duplicate, in which case we repeat
            if(nums[start] == nums[end]){
                return true;
            }
            else{
                //we checked all against the first number - now we move the start to the next item on list
                //so our new START is (start+1) and our new END (length-1)
                return recursion(nums, (start+1), (nums.length-1));
            }
        }
        else{
            if(end < 0){return false;}
            //here you evaluate if the start and end numbers are different 
            if(nums[start] == nums[end]){return true;}          
            return recursion(nums, start, (end - 1));          
        }       
    }

请将您的"递归"函数替换为上面的代码，让我们看看它是否适合您。

Answer 4

蛮力方法：

步骤：

• 你可以使用外部循环来迭代 nums 数组，直到长度为 1
• 内部循环可以从 i+1 开始，直到 nums.length
• 在每次迭代中，我们可以比较 数字[i]和数字[j]
• 如果两个值都相等，那么我们可以返回 true，否则返回 false
• 由于它是蛮力方法，因此需要 O（n^2） 时间复杂度。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        for(int i = 0; i<nums.length-1; i++){
            for(int j = i+1; j<nums.length; j++){
                if(nums[i] == nums[j]){
                    return true;
                }
            }
        }
        return false;
    }
}

Answer 5

    bool containsDuplicate(vector<int>& nums) {
    unordered_map<int,int>m;
    for(int i = 0; i<nums.size(); i++){
        if(m.count(nums[i]) > 0){
            return true;
        }
        else
        {
            m[nums[i]] = i;
        }
            
    }
    return false;
    
}

Answer 6

一个更简洁的解决方案是

class Solution {
    public boolean containsDuplicate(int[] nums) {
       Set<Integer> set = new HashSet<Integer>();
        for(int x:nums)
        {
            set.add(x);
        }
        if(set.size()==nums.length)return false;
        return true;
    }

}