求高效生成满足i≤j的数组索引对列表的非双重循环方案

首先明确核心事实：满足i≤j的索引对总数为N(N+1)/2，这是数学上的固定值，因此无论采用何种方法，生成所有索引对的时间复杂度必然是O(N²)——这是无法突破的下限。现有双重循环和回溯方法的问题，更多在于内存占用而非时间效率，尤其是处理千级以上数组时，一次性存储所有索引对会带来巨大内存压力。

以下是针对不同场景的优化方案：

一、无需存储所有索引对：用生成器逐对产出 #

如果你的业务逻辑只需要逐个处理索引对（而非一次性持有全部），使用生成器可以将内存复杂度降到O(1)，仅在当前处理时保留单个索引对，彻底避免大数组内存溢出问题。

function* generateIndexPairs(arrLength) {
  for (let i = 0; i < arrLength; i++) {
    // 先产出(i,i)的情况
    yield [i, i];
    // 再产出i<j的所有情况
    for (let j = i + 1; j < arrLength; j++) {
      yield [i, j];
    }
  }
}

// 使用示例：逐个处理索引对
const pairGenerator = generateIndexPairs(1000);
let currentPair = pairGenerator.next();
while (!currentPair.done) {
  // 这里替换为你的业务处理逻辑
  console.log(currentPair.value);
  currentPair = pairGenerator.next();
}

二、必须存储所有索引对：优化存储结构 #

如果业务需求要求必须持有全部索引对，重点优化方向是减少内存占用。JavaScript中可以使用**类型化数组（TypedArray）**替代普通数组，因为TypedArray的内存是连续的固定大小空间，没有普通数组的额外对象开销，内存占用可降低约50%以上。

function generatePairsArray(arrLength) {
  const totalPairs = (arrLength * (arrLength + 1)) >> 1;
  // 使用Uint32Array存储，每个索引占32位整数，适配绝大多数数组长度
  const pairs = new Uint32Array(totalPairs * 2);
  let ptr = 0;
  
  for (let i = 0; i < arrLength; i++) {
    pairs[ptr++] = i;
    pairs[ptr++] = i;
    for (let j = i + 1; j < arrLength; j++) {
      pairs[ptr++] = i;
      pairs[ptr++] = j;
    }
  }
  
  // 如需转换为普通数组格式，可按需处理
  // return Array.from(pairs).reduce((acc, val, idx) => {
  //   if (idx % 2 === 0) acc.push([val]);
  //   else acc[acc.length-1].push(val);
  //   return acc;
  // }, []);
  
  return pairs;
}

对现有方法的补充说明 #

• 双重循环是时间效率最优的实现，本身没有可优化的空间，但直接存储所有[i,j]数组会带来大量内存开销；
• 回溯方法的效率反而低于双重循环，因为存在额外的函数调用和栈操作开销，不建议在大数组场景使用。

内容的提问来源于stack exchange，提问作者Lindy T