做算法题有个挺有意思的规律：题目越简单，越能看出思路的差距。暴力解法往往很快就能写出来，但想出更优雅的解法，可能需要多琢磨一会儿。下面这三道题都是 LeetCode 上的简单题，我把自己第一次做时的思路和后来学到的更好写法整理了一下。
题一：存在重复元素
题目：给一个整数数组，判断里面有没有重复的数字。
我最先想到的写法
看到"有没有重复"，第一反应肯定是拿每个数跟后面的数都比一遍：
#include <stdbool.h> bool containsDuplicate(int nums[], int numsSize) { for (int i = 0; i < numsSize; i++) { for (int j = i + 1; j < numsSize; j++) { if (nums[i] == nums[j]) { return true; } } } return false; }这代码写起来很顺，但问题也很明显：两层循环，时间复杂度是O(n²)。数组稍长一点，LeetCode 就会报超时。
更好的思路：排个序再看
其实有个特别简单的转化：如果数组是有序的，相同的数字一定会挨在一起。那我们先排序，然后只需要扫一遍，看看相邻的两个数相不相等就行了。
为了代码好懂，这里用冒泡排序（纯数组下标操作，不涉及指针）：
#include <stdbool.h> bool containsDuplicate(int nums[], int numsSize) { // 冒泡排序 for (int i = 0; i < numsSize - 1; i++) { for (int j = 0; j < numsSize - 1 - i; j++) { if (nums[j] > nums[j + 1]) { int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } // 排序后检查相邻元素 for (int i = 0; i < numsSize - 1; i++) { if (nums[i] == nums[i + 1]) { return true; } } return false; }关键点：排序把时间复杂度降到了O(n log n)（虽然教学代码里写的是冒泡，实际工程中换成快速排序就行），后面的扫描是O(n)。整体比暴力解法快太多了。
题二：罗马数字转整数
题目：给一个罗马数字字符串，转成对应的整数。
我最先想到的写法
一开始我直接把六种减法特例全写成了if-else，比如看到I就判断后面是不是V或X，是的话就减 1，否则加 1：
int romanToInt(char s[]) { int result = 0; int len = 0; while (s[len] != '\0') len++; for (int i = 0; i < len; i++) { if (s[i] == 'I') { if (i + 1 < len && (s[i+1] == 'V' || s[i+1] == 'X')) { result -= 1; } else { result += 1; } } else if (s[i] == 'X') { if (i + 1 < len && (s[i+1] == 'L' || s[i+1] == 'C')) { result -= 10; } else { result += 10; } } // ... 后面还有 C、V、L、D、M 的一大堆判断 // 代码太长，这里省略了 } return result; }这代码能跑，但写起来特别繁琐，而且逻辑分散。万一规则再多几条，代码还会继续膨胀。
更好的思路：其实规律只有一条
仔细观察会发现，罗马数字的减法规则可以归纳成一句话：
如果当前字符的值 < 右边字符的值，当前字符做减法；否则做加法。
比如IV：I(1) < V(5)，所以 I 减；VI：V(5) >= I(1)，所以 V 加。
利用这个规律，我们建一个"字符到数值"的映射表，然后从左到右扫一遍就行：
int romanToInt(char s[]) { int map[256] = {0}; map['I'] = 1; map['V'] = 5; map['X'] = 10; map['L'] = 50; map['C'] = 100; map['D'] = 500; map['M'] = 1000; int result = 0; int len = 0; while (s[len] != '\0') len++; for (int i = 0; i < len; i++) { int current = map[(unsigned char)s[i]]; int next = (i + 1 < len) ? map[(unsigned char)s[i + 1]] : 0; if (current < next) { result -= current; } else { result += current; } } return result; }关键点：把一堆特例压缩成了一个统一的判断条件，代码简洁了很多。时间复杂度O(n)，空间复杂度O(1)，已经是这道题的最优解。
题三：最长公共前缀
题目：给一个字符串数组，找出所有字符串的最长公共前缀。
我最先想到的写法
我当时的做法是：先求第 0 个和第 1 个字符串的公共前缀，再用这个结果和第 2 个字符串求公共前缀，依此类推。
// 辅助函数：求两个字符串的公共前缀长度 int commonPrefix(char a[], char b[]) { int i = 0; while (a[i] != '\0' && b[i] != '\0' && a[i] == b[i]) { i++; } return i; } char* longestCommonPrefix(char** strs, int strsSize) { if (strsSize == 0) return ""; int minLen = commonPrefix(strs[0], strs[1]); for (int i = 2; i < strsSize; i++) { int len = commonPrefix(strs[0], strs[i]); if (len < minLen) minLen = len; } strs[0][minLen] = '\0'; return strs[0]; }这个思路没问题，但写起来比较繁琐，需要额外的辅助函数，而且每次两两比较时，前面的字符会被反复扫描。
更好的思路：纵向扫描
换个角度看问题：公共前缀其实就是所有字符串在相同位置上的字符都一样。那我们可以一列一列地检查，而不是一个字符串一个字符串地比较。
char* longestCommonPrefix(char** strs, int strsSize) { if (strsSize == 0) return ""; int col = 0; // 当前检查第几列 while (1) { char c = strs[0][col]; // 拿第一个字符串的第 col 个字符当基准 if (c == '\0') break; // 第一个字符串到头了 int match = 1; for (int row = 1; row < strsSize; row++) { if (strs[row][col] != c) { match = 0; break; } } if (!match) break; // 这一列有不匹配的，前缀到此为止 col++; } strs[0][col] = '\0'; // 截断，剩下的就是最长公共前缀 return strs[0]; }关键点：把"字符串之间的比较"转化成了"矩阵按列的检查"。一旦发现某一列不匹配，立刻停止，不需要再往后看。代码更紧凑，而且避免了重复比较。
