AI工具人

# 5种解法的算法面试题 来看看你是青铜还是王者?

## 青铜-暴力求解

``````    public int[] find(int[] arr, int target) {
for (int s = 0; s &lt; arr.length; s++) {
for (int e = s+1; e &lt; arr.length; e++) {
int sum = 0;
for (int k = s; k &lt;= e; k++) { // 求s到e之间的和
sum += arr[k];
}
if (target == sum) {
return new int[]{s, e};
}
}
}
return null;
}``````

## 白银-空间换时间

``````    public int[] find(int[] arr, int target) {
int[] sumArr = new int[arr.length + 1];
for (int i = 1; i &lt; sumArr.length; i++) {
sumArr[i] = sumArr[i-1] + arr[i-1];  // 预处理，获取累计数组
}
for (int s = 0; s &lt; arr.length; s++) {
for (int e = s+1; e &lt; arr.length; e++) {
if (target == sumArr[e+1] - sumArr[s]) {
return new int[]{s, e};
}
}
}
return null;
}``````

## 黄金-二分查找

``````    public int[] find(int[] arr, int target) {
int[] sumArr = new int[arr.length + 1];
for (int i = 1; i &lt; sumArr.length; i++) {
sumArr[i] = sumArr[i-1] + arr[i-1];
}
for (int s = 0; s &lt; arr.length; s++) {
int e = bSearch(sumArr, sumArr[s] + target);
if (e != -1) {
return new int[]{s, e};
}
}
return null;
}
// 二分查找
int bSearch(int[] arr, int target) {
int l = 1, r = arr.length-1;
while (l &lt; r) {
int mid = (l + r) &gt;&gt; 1;
if (arr[mid] &gt;= target) {
r = mid;
} else {
l = mid + 1;
}
}
if (arr[l] != target) {
return -1;
}
return l - 1;
}``````

## 钻石-HashMap优化

``````    public int[] find(int[] arr, int target) {
int[] sumArr = new int[arr.length + 1];
Map&lt;Integer, Integer&gt; map = new HashMap&lt;&gt;();
for (int i = 1; i &lt; sumArr.length; i++) {
sumArr[i] = sumArr[i-1] + arr[i-1];
map.put(sumArr[i], i-1);
}

for (int s = 0; s &lt; arr.length; s++) {
int e = map.getOrDefault(sumArr[s]+target, -1);
if (e != -1) {
return new int[]{s, e};
}
}
return null;
}``````

## 王者-尺取法

``````    public int[] find(int[] arr, int target) {
int s = 0, e = 0;
int sum = arr[0];
while (e &lt; arr.length) {
if (sum &gt; target) {
sum -= arr[s++];
} else if (sum &lt; target) {
sum += arr[++e];
} else {
return new int[]{s, e};
}
}
return null;
}``````