3-sum問題を分析する(Three sum)

日常生活の中でよく配列の中で存在するかどうかと0の3つの数、すなわち3-sumの問題を解くことに出会って、そのため本文はいくつかの比較的に実用的な方法を紹介して、そして暴力の計算の基礎の上でアルゴリズムに対して次第に改善して、最も良いアルゴリズムを達成します.
まず2-sum問題を紹介しますが、3-sum問題は実は2-sum問題の拡張です.2−sum問題では,2層ループを用いて配列中のすべての要素対を直接列挙し,0の要素対が見つかるまで行うことが最も一般的な考え方である.

int sum_2()
{
	int res = 0;
	int n = data.size();
	for(int i=0; i

上記のアルゴリズムは2層のループを含んでいるため,時間的複雑度はO(N^2)である.
観察により,上記のアルゴリズム時間は主にデータペアリングに費やされるため,二分ルックアップを用いてデータペアリング時間を減らすことが考えられ,二分ルックアップを用いるにはまずデータをソートし,ここでは集計ソートを用いて配列を昇順に配列する必要がある.ソートにかかる時間はO(NlogN)であり、ソート後のデータ検索にはO(logN)の時間しかかかりませんが、合計でNを検索する必要があります.このため、改善後のアルゴリズムの時間複雑度はO(NlogN)です.

int cal_sum_2()
{
	int res = 0;
	for(int i=0; i i)	
		res++;
	}
	return res;
}

上記のアルゴリズムを観察すると、比較の過程でいくつかの冗長性があることが分かった.配列後のデータは最小の数から一致するので、最後のデータとの和が0であるかどうかを計算するだけでよいが、0より大きい場合は最小数に一致する数が存在しないことを示し、この場合は最大の数を小さい数で置き換え、逆に最小の数を大きい数で置き換えるという繰り返しである.配列を1回スキャンするだけで、条件に合致するすべての要素ペアが得られます.このアルゴリズムにかかる時間は,主に配列ソートの時間,すなわちO(Nlogn)である.

int cal_sum_2_update()
{
	int res = 0;
	for(int i=0,j=data.size()-1; i 0)
			j--;
		else if(data[i] + data[j] < 0)
			i++;
		else
		{
			res++;
			j--;
			i++;
		}
	}
	return res;
}

上記2-sumの解題構想は3-sumおよび4-sum問題に適用され、例えばa+b+c=0を解くと、それをa+b=-cを解くことに変換することができ、これは2-sum問題である.このため,2−sum,3−sum,4−sumの解法および対応する最適化法を以下に示すsumクラスに実装した.

sum   

#ifndef SUM_H
#define SUM_H
#include 
using std::vector;
class sum
{
private:
	vector data;
public:
	sum(){};
	sum(const vector& a);
	~sum(){};
	int cal_sum_2() const;
	int cal_sum_3() const;
	int cal_sum_4() const;
	int cal_sum_2_update() const;
	int cal_sum_3_update() const;
	int cal_sum_3_update2() const;
	int cal_sum_4_update() const;
	void sort(int low, int high);
	void print() const;
	friend int find(const sum& s, int target); 
};
#endif

sum   

#include "Sum.h"
#include 
using namespace std;
sum::sum(const vector& a)
{
	data = a;
}
void sum::sort(int low, int high)
{
	if(low >= high)
		return;
	int mid = (low+high)/2;
	sort(low,mid);
	sort(mid+1,high);
	vector temp;
	int l = low;
	int h = mid+1;
	while(l<=mid && h <=high)
	{
		if(data[l] > data[h])
			temp.push_back(data[h++]);
		else
			temp.push_back(data[l++]);
	}
	while(l<=mid)
		temp.push_back(data[l++]);
	while(h<=high)
		temp.push_back(data[h++]);
	for(int i=low; i<=high; i++)
	{
		data[i] = temp[i-low];
	}
}
void sum::print() const
{
	for(int i=0; i target)
		{
			high = mid - 1;
		}
		else
		{
			return mid;
		}
	}
	return -1;
}
int sum::cal_sum_2() const
{
	int res = 0;
	for(int i=0; i i)	
			res++;
	}
	return res;
}
int sum::cal_sum_3() const
{
	int res = 0;
	for(int i=0; i 0)
			j--;
		else if(data[i] + data[j] < 0)
			i++;
		else
		{
			res++;
			j--;
			i++;
		}
	}
	return res;
}
int sum::cal_sum_3_update() const
{
	int res = 0;
	for(int i=0; i j)
				res ++;
		}
	}
	return res;
}
int sum::cal_sum_3_update2() const
{
	int res = 0;
	for(int i=0; i -data[i])
				p--;
			else
			{
				res++;
				j++;
				p--;
			}
		}
	}
	return res;
}
int sum::cal_sum_4_update() const
{
	int res = 0;
	for(int i=0; ip)
					res++;
			}
		}
	}
	return res;
}

#include "Sum.h"
#include 
#include 
#include 
using namespace std;
void main()
{
	ifstream in("1Kints.txt");
	vector a;
	while(!in.eof())
	{
		int temp;
		in>>temp;
		a.push_back(temp);
	}
	sum s(a);
	s.sort(0,a.size()-1);
	s.print();
	cout<

上記のアルゴリズム設計の考え方は、今後アルゴリズムを学ぶ過程で役立つことを望んでいます.