判断数组是否包含重复的字符串

[题目链接](https://www.nowcoder.com/practice/aec7ce39075142719339a0e77115f4f3)

思路

本题要求判断一组字符串中是否存在重复。

哈希集合判重

最直接的方法是利用哈希集合（HashSet）：依次读入每个字符串，尝试将其加入集合。如果加入失败（说明集合中已存在该字符串），则存在重复，输出 true；如果所有字符串都能成功加入，则无重复，输出 false。

等价地，也可以先把所有字符串读入数组，比较数组长度和去重后集合大小是否相等。

样例演示

  • 输入 hello world：两个不同的字符串，集合大小等于数组长度，输出 false。
  • 输入 hello world in programming world：world 出现了两次，输出 true。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    set<string> seen;
    bool dup = false;
    while(cin >> s){
        if(!seen.insert(s).second){
            dup = true;
        }
    }
    cout << (dup ? "true" : "false") << endl;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<String> seen = new HashSet<>();
        boolean dup = false;
        while (sc.hasNext()) {
            String s = sc.next();
            if (!seen.add(s)) {
                dup = true;
            }
        }
        System.out.println(dup ? "true" : "false");
    }
}

import sys

words = sys.stdin.read().split()
print("true" if len(words) != len(set(words)) else "false")

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    const words = lines.join(' ').split(/\s+/).filter(s => s.length > 0);
    const seen = new Set(words);
    console.log(seen.size !== words.length ? "true" : "false");
});

复杂度分析

设 为字符串数组的长度， 为单个字符串的最大长度。

  • 时间复杂度：，每个字符串插入哈希集合的时间为 ，共 个字符串。
  • 空间复杂度：，哈希集合最多存储 个字符串。